TimothyQiu's Blog

keep it simple stupid

SSOAAG

分类:技术

好吧,标题的意思其实是 Some Sort Of Ascii Art Generator……

把这两天的无聊成果放 GitHub 上了,按标题的意思可以理解为某种字符画生成器。

一句话解释原理

在一个 HTML 文档里,把一系列「■」字符作为像素点,并用 <span> 元素为每一个字符指定颜色。再把行距、字间距变小,就形成了一个画布。把图片中每一个像素的颜色赋值给对应的「■」字符就可以产出该图片的马赛克版本(类似于放大 N 倍后的效果)。而根据这个像素点的颜色值可以计算出灰度,再根据灰度的深浅选择相应的字符代替「■」字符(比如灰度小于 64 选 @、小于 128 选 :、其余选 .),就可以产出该图片的字符画版本了。

好吧,这不是一句话,这是一段话 Orz...

Bitmap

嗯,挑了个很矬的名字命名这个类。Bitmap 类主要是为了读取位图文件中的颜色数据而生的。在 Load 时解析位图文件内容,无论原来是什么格式,内部都用 0xAARRGGBB 的形式保存……………………(这是设想)

现实:色深和压缩方式好多……于是目前只把最简单的未压缩版本的 1位色(黑白)/ 4位色 / 8位色 / 16位色 / 24 位色 / 32 位色位图读取实现了。

于是 DIB Header 是 BITMAPINFOHEADER 版本及以后的未压缩位图应该都可以读取了,理论上 4 色位图也支持读取,但我真心没有找到可以产出一个 4 色位图的办法,汗~

程序崩溃的善后工作

分类:技术

说来,写 C/C++ 的程序,由于指针的存在,程序崩溃什么的也就没什么大惊小怪的了。人非圣贤,孰能无过嘛,而且个人觉得程序崩溃比出现错误的结果好调试多了:在 Visual Studio 里 Debug 版本 F5 调试运行直接可以断在崩溃的地方,方便调试。但 Release 版本就没这么幸运了 :(

如果说单纯是是调试 Release 版本,我只用过《游戏之旅》中介绍的勾选 Linker 选项中的 Generate Map File,然后通过崩溃提示信息中提供的 EIP 查这个 Map File 找到崩在哪个函数里,兴致高一点的根据反汇编一步步走下去兴许还能知道是崩在哪句上 :)

不过说到最终交付出去的程序,面对可能存在的各种未知问题,还是生成 Dump 文件,把崩溃那一刻的信息写进文件以供日后分析比较靠谱。

捕捉未捕获的异常

好吧,Windows API 提供了 SetUnhandledExceptionFilter 函数来设置在发生未捕获的异常时调用的回调函数(仅在程序不处于调试运行时调用)。例如设置 CrashCallback 函数:

#include <windows.h>

LONG WINAPI CrashCallback(EXCEPTION_POINTERS *exceptionInfo)
{
    // 崩溃处理
    return EXCEPTION_EXECUTE_HANDLER;
}

int main()
{
    SetUnhandledExceptionFilter(CrashCallback);
    // 程序段
}

回调时传入的参数 exceptionInfo 保存了关于该异常的详细信息,不过 Dump 的输出可以不需要亲自干预太多。

生成 Dump 文件

利用上面回调中给出的 EXCEPTION_POINTERS 结构指针提供的信息,MiniDumpWriteDump 函数即可按要求输出一个 Dump 文件内容,其原型:

BOOL WINAPI MiniDumpWriteDump(
    HANDLE hProcess,         // Dump 目标进程句柄
    DWORD ProcessId,         // Dump 目标进行 ID
    HANDLE hFile,            // 输出文件句柄
    MINIDUMP_TYPE DumpType,  // 输出类型,决定输出哪些内容
    MINIDUMP_EXCEPTION_INFORMATION *ExceptionParam,
    MINIDUMP_USER_STREAM_INFORMATION *UserStreamParam,
    MINIDUMP_CALLBACK_INFORMATION *CallbackParam
);

输出 Dump 文件的内容根据 DumpType 参数变化,详见 MSDN 关于 MINIDUMP_TYPE 的条目。这里举例输出一个最小的 Dump 文件:

HANDLE hFile = CreateFile(TEXT("filename.dmp"), GENERIC_READ | GENERIC_WRITE,
    0, NULL, CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, NULL);

if ((hFile != NULL) && (hFile != INVALID_HANDLE_VALUE)) {
    MINIDUMP_EXCEPTION_INFORMATION mdei;

    mdei.ThreadId          = GetCurrentThreadId();
    mdei.ExceptionPointers = exceptionInfo;
    mdei.ClientPointers    = FALSE;

    MiniDumpWriteDump(GetCurrentProcess(), GetCurrentProcessId(),
                      hFile, MiniDumpNormal, &mdei, NULL, NULL);
    CloseHandle(hFile);
}

需要注意的是,MiniDumpWriteDump 等声明在 DbgHelp.h 中,需要链接 DbgHelp.lib。当然也可以自行从 DbgHelp.dllLoadLibrary 之。

Dump 文件的使用

Dump 文件是可以用 WinDbg 打开的,不过因为手头没有这东西所以没有试过 =3=

Dump 文件也可以用 Visual Studio 打开,而且(似乎)方便一些:把 dmp 文件、exe 文件、pdb 文件放在同一目录中,然后用 Visual C++ 打开 dmp 文件即出现 Minidump File Summary 页面。可以查看异常信息,或者使用右侧的调试按钮开始调试运行并直接断在崩溃处。

以上,就是好久以来的流水帐……

常用排序算法

分类:技术

选择排序 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. 悲催的是今天决定自己写修改器其实是因为懒得下载安装《金山游侠》,但结果写到最后,还是把《金山游侠》下了下来做测试用了……

C++ 中 protected 成员的坑爹来历

分类:技术,闲扯

嗯哼~坑爹的保护成员果然有个坑爹的来历。作为 C++ 之父的 Bjarne Stroustrup 大叔在他的大作 The Design and Evolution of C++ 中写道:(以下引自中文版《C++ 语言的设计和演化》,第 13.9 节)

在 Release 1.0 推出后不久,Mark Linton 顺便到我的办公室来了一下,提出了一个使人印象深刻的请求, 要求提供第三个控制层次,一边能直接支持斯坦福大学正在开发的 Interviews 库中所使用的风格。我们一 起揣摩,创造出单词 protected 以表示类里的一些成员,它们对于这个类和它的派生类“像公用的”,而对其 他地方就“像私用的”。

Mark 是 Interviews 的主要设计师。它的有说服力的争辩是基于实际经验和来自真实代码的实例。他论证 说,保护数据对于设计一个高效的可扩充的 X 窗口工具包是最关键的东西,而可能替代保护数据的其他方式 都因为低效、难以处理在线界面函数或者使用数据公开等等,因而是无法接受的。

…(略)…

大约五年之后,Mark 在 Interviews 里禁止了保护数据成员,因为它们已经变成许多程序错误的根源 …(略)… 实际上,我对 protected 的关心正在于它将导致使用一个基类变得太容易,就像人们可能因为懒惰而使用全局数据一样。

…(略)…

保护成员是 Release 1.2 引进的,保护基类最早是在 ARM 里描述的,Release 1.2 提供了它。回过头看,我认为 protected 是“好的论据”和时尚战胜了我的更好的判断和经验规则,使我接受新特征的一个例子。

话说我能顺便吐槽下这悲催的中文翻译么?最后一段完全不是翻给地球人看的嘛 :P