TimothyQiu's Blog

keep it simple stupid

常用排序算法

分类:技术

选择排序 Selection sort

每次从尚未排好的数组范围里选出一个最小的放到正确的位置。

C 语言版本:

void selection_sort(int array[], int size)
{
    int lhs, rhs;
    int min;

    for (lhs = 0; lhs < size - 1; lhs++) {
        min = lhs;
        for (rhs = lhs + 1; rhs < size; rhs++) {
            if (array[rhs] < array[min])
                min = rhs;
        }
        swap(array, lhs, min);
    }
}

C++ 版本:

template <typename Iter, typename Compare>
void selectionSort(Iter begin, Iter end, Compare compare)
{
    for (auto iter = begin; iter != end; ++iter) {
        std::iter_swap(iter, std::min_element(iter, end, compare));
    }
}

快速排序 Quicksort

从数组里选出一个基准元素,通过交换位置让它前面的元素都比它小、后面的元素都比它大,最后分而治之。

C++ 版本:

template <typename Iter, typename Compare>
void quickSort(Iter begin, Iter end, Compare compare)
{
    auto distance = std::distance(begin, end);
    if (distance > 1) {
        auto const pivot = std::next(begin, distance / 2);
        std::nth_element(begin, pivot, end, compare);
        quickSort(begin, pivot, compare);
        quickSort(pivot, end, compare);
    }
}

插入排序 Insertion sort

每次从尚未排好的数组范围取出一个元素,放到已排好的数组范围中的正确位置。(现实生活中排序时一般用的就是类似这种算法)

C 语言版本:

void insertion_sort(int array[], int size)
{
    int lhs, rhs;
    int cur;

    for (rhs = 1; rhs < size; rhs++) {
        cur = array[rhs];
        for (lhs = rhs - 1; (lhs > 0) && (array[lhs] > cur); lhs--)
            array[lhs + 1] = array[lhs];
        array[lhs] = cur;
    }
}

C++ 版本:

template <typename Iter, typename Compare>
void insertionSort(Iter begin, Iter end, Compare compare)
{
    for (auto iter = begin; iter != end; ++iter) {
        std::rotate(std::upper_bound(begin, iter, *iter, compare),
                    iter,
                    std::next(iter));
    }
}

堆排序 Heapsort

保持未排数组为堆积树,每次摘取根结点,即可取出当前未排范围中的最大/最小值放入正确位置。

C 语言版本:

void sift_down(int heap[], int root, int end)
{
    int l_child = root * 2 + 1;
    int r_child = root * 2 + 2;
    int max = root; // max heap

    if (l_child <= end && heap[l_child] > heap[max])
        max = l_child;

    if (r_child <= end && heap[r_child] > heap[max])
        max = r_child;

    if (max != root) {
        swap(heap, max, root);
        sift_down(heap, max, end);
    }
}

void heapsort(int array[], int size)
{
    int i;

    // from last parent node
    for (i = (size - 2) / 2; i >= 0; i--)
        sift_down(array, i, size - 1);

    for (i = size - 1; i > 0; i--) {
        swap(array, 0, i);
        sift_down(array, 0, i - 1);
    }
}

C++ 版本:

template <typename Iter, typename Compare>
void heapSort(Iter begin, Iter end, Compare compare)
{
    std::make_heap(begin, end, compare);
    std::sort_heap(begin, end, compare);
}

嗯,基本上常用的就是这些啦~

什么,没有冒泡排序?好吧,我至今都想不明白像冒泡排序这样写起来没有选择排序方便、想起来没有插入排序方便的排序算法是怎么成为教科书中的天字第一号排序算法的。嗯……连奥巴马都知道不能用冒泡排东西。

最后,别忘了还有睡眠排序这样神奇的存在 :)

p.s. 代码里的交换两个元素的值,美观起见就直接写 swap 啦,具体实现随便挑 :)

写游戏修改器的流水账

分类:技术

昨天很郁闷的在玩《仙剑五》打七圣的时候被太武老爷子调戏了三四个小时,于是玩游戏一贯很讨厌用作弊器的俺打起了作弊的念头。因为懒得找专用修改器和《金山游侠》(软件名称应该打书名号,但总有点怪怪的)的下载,作为一个死程,自然是要自己动手写代码咯~

基本原理非常之简单:既然程序运行时所需数据都保存在内存中,那么如果要修改游戏里的某项数值的话,直接去保存数值的地方修改就好了。

首要问题在于:茫茫内存,我他喵的怎么知道 HP 存哪儿去了?

嘛~用过《金山游侠》的都知道这么一个流程,比如要修改 HP: 1. 记下当前的 HP,按「搜索」,下面一个列表里会显示一大堆「搜索结果」; 2. 如果结果不唯一,进游戏修改自己的 HP(比如嗑药)后重复第1步; 3. 此时剩下的结果显示的就是保存 HP 的地方了。

也就是说,要在该进程所占的所有内存地址中不断筛选所存值与 HP 值相同的地址。

打开进程需要先获得进程ID,最简单的方法可以通过 EnumWindows -> GetWindowThreadProcessId 的流程枚举获得各个窗口对应的进程ID,但我这么做以后运行时一直提示「无法定位程序输入点 GetWindowThreadProcessId」,各种搜索未果后就放弃了好吧,不久后我又发现这么做木有问题了;另一种方法是改按 CreateToolhelp32Snapshot -> Process32First -> Process32Next 的流程获得各进程ID。(=ω= 忽然很萌这种 API 接 API 的「流程」……)

获得进程ID后就可以用 OpenProcess 获得进程句柄,剩下的工作就是遍历该进程所占内存。

于是又来一个问题:从哪儿遍历到哪儿?即使是 32 位系统,要遍历 0x00000000~0xFFFFFFFF 的话你也伤不起啊!

幸好这个范围是可以缩小的:

首先,我们知道,虽然 Windows 下每个应用程序可以认为「独占」所有地址,但也只是「认为」而已。实际可访问地址的上下限可以通过 GetSystemInfo 获取。

然后,在这个上下限范围内,也并不是所有内存都已分配,更不是所有内存都可读写(「不可写」即该进程自己也不可写,那么是纯常量或者程序段,肯定存不了HP数据)。可以通过 VirtualQueryEx 函数获取各段内存的信息,从而筛选出我们最终需要分析的地址范围。

那么,在之前得到的内存片段里,就可以用 ReadProcessMemory 读取指定地址、指定大小的数据了。经历若干次筛选,地址确定后,可以用 WriteProcessMemory 改写指定地址、指定大小的数据,这样就实现了游戏的修改,最基本的内存修改器也就是这样的了。

ps. 悲催的是今天决定自己写修改器其实是因为懒得下载安装《金山游侠》,但结果写到最后,还是把《金山游侠》下了下来做测试用了……

Lua 学习笔记:C API 遍历 Table

分类:技术

前情提要

Lua 通过一个虚拟栈与 C 的交互,正数索引自底向上取值,负数索引自顶向下取值。

Lua 中的 Table(表)结构可以使用任何数据作为 key 进行取值。使用 C API 访问 Table 中的元素有两种方法:

lua_getglobal(L, t);
lua_pushinteger(L, k); -- 这里可以换成其它类型的 lua_pushXXXX(L, k) 压数据到栈顶作key
lua_gettable(L, -2);

lua_getglobal(L, t);
lua_getfield(L, -1, k);

在结束时,栈上的情况均为:栈顶为 t[k],次顶元素为 Table 类型的 t。第二种方法其实是第一种方法在「key 为字符串」时的特殊写法。

C API 遍历 Table

lua_getglobal(L, t);
lua_pushnil(L);
while (lua_next(L, -2)) {
    /* 此时栈上 -1 处为 value, -2 处为 key */
    lua_pop(L, 1);
}

lua_next 函数针对 -2 处(参数指定)的 Table 进行遍历。弹出 -1 处(栈顶)的值作为上一个 key(为 nil 时视为请求首个 key),压入 Table 中的下一个 key 和 value。返回值表示是否存在下一个 key。

lua-next

另外在循环中处理值时要记得随时清理栈,否则 Table 就不在 -2 了。(也可以考虑在 lua_getglobal 后用 lua_gettop 存下 Table 的正数索引。)

虽然这是手册中记载的遍历方法,但这种方法在遍历时并没有一定的遍历顺序,于是便又有了下面的方法。

用整数 Key 进行并不那么完美的遍历

lua_getglobal(L, t);
len = lua_objlen(L, -1);
for (i = 1; i <= len; i++) {
    lua_pushinteger(L, i);
    lua_gettable(L, -2);
    /* 此时栈顶即为 t[i] 元素 */
    lua_pop(L, 1);
}

这种方法无视了非整数 key,但可以保证遍历顺序。如果只关注整数 key,可以考虑用这种遍历方法 :)

String as Array Index

分类:技术

标题用中文写觉得比较怪(用字符串作为数组下标),那就写英文吧~

话说前几天人人网 C 语言公共主页发了篇日志,内容是腾讯的面试题:

int a = 3, b = 5;
printf(&amp;a["Hi!Hello"],&amp;b["fun/super"]);
printf("%c%c%c%c",1["wst"],2["www"],0["ddd"],5["ewewrew"]);

这段代码应该输出什么呢?答案是应该输出:

Helloswde

主页君说没遇到过这类语法,于是把编译后的程序反汇编了说明为什么是这个答案。

但事实上,类似 a["Hi!Hello"] 的语法和普通数组 a[3] 的用法并没有什么两样。

我们知道,C 语言的数组直接对应一片连续的内存,数组名代表起始地址,要访问数组元素就要用方括号中的表达式代表该元素的偏移量。类似 array[index] 的表达式实际上等价于

*(array + index)

由于指针算术(Pointer Arithmetic)的关系,表达式可以正确得到 array 指针向后指 index 个元素的值(前提是 arrayindex 两者中有且只有一个指针,否则该表达式无效)。所以 array[index]index[array] 其实没什么两样。

那么,既然 C 语言字符串本质是字符数组的首地址,3 + "Hi!Hello" 就是一个指向字符串3号元素的字符指针,传给 printf 即从第4个字符开始输出到 '\0'

所以说,这道面试题其实是非常巧妙的基础题。但悲催的是,那篇日志下的评论不少是“考这个有鸟用”、“TX就会这种傻逼题”、“考这么偏的点”,真是让人感到悲哀……