晚安短信 day 6

发表于 阅读次数： 本文字数： 7.8k 阅读时长 ≈ 7 分钟

本文与原始版本相比有删改，删除了部分个人信息和无关内容。请注意原始版本发布的时间。

亲爱的朋友：

晚上好，转眼就到周末了，今天我写了很久的大程，基本上全部完工了。

另外，今天下午带一个高中同学逛了紫金港，上次我去浙工大考六级的时候，他也带我转了转。然后我们高中的几个在杭的 OIer （包括之前那位朋友）聚了聚，有几位在港，有几位是下沙一带的学校。还有一位从 hku 来各地玩，今天到了杭州，貌似已经考完期末考试了，真羡慕。晚上一起吃了顿烧烤。没想到今晚例会还有吃的，真不错。

大程

由于必须要用比较垃圾的 imgui，而我又引入了 Win32 的通用控件，而且在 Windows 10 下完全扁平化，导致界面风格明显割裂，不过我也没什么办法。

尽管我没有系统学过标准的 Windows 编程，但通过大量查阅 Microsoft Docs 我也了解了不少，什么HWND, HDC, HINSTANCE, WPARAM等等。下面我简单回顾一下遇到的各种问题。

纯 C 真是垃圾

由于大程要求必须用纯 C 写，虽然我怀疑我偷偷改一下编译选项，稍微写点 C++ 也不一定有人会发现。不过我还是比较认真的用 C 写，不过用的是 C99，毕竟连 pintia 也用 C99 标准。用 C99 主要是可以随处定义变量（C89 或 ANSI C 就必须定义在语句块开始处！），还有一个我很习惯用的for (int i = 0; i < n; i++)，也就是在for里面定义循环变量。

C 在写大程中的缺点，相比最为熟悉的 C++，我可以归纳为不支持面向对象、不支持名称空间/包、不支持模板等。不支持面向对象，就导致控制代码非常散乱，很多时候很难找到。名称空间，或者像 Go 或 Python 的包也很重要，没有它就不得不取名字很长的标识符来防止重名。当然如果支持面向对象，那么都塞进对象也是一样的道理。至于模板，是因为按照要求我需要实现int, float, double三种类型的数据，虽然可以都塞进double里而不造成任何误差，但毕竟不规范，而且我怀疑看代码的人也不一定能理解 IEEE 标准。如果有模板，就直接T过去就好了。

彩色的归并排序

(1)上的归并排序是彩色的，我看了非常喜欢，也想自己实现一个。不过要实现彩虹渐变色，需要一个 HSL 转 RGB 的函数，之前技术分享我就提过，在 mspaint 里调 HSL 是我童年一大乐趣呢。但是 HSL 比较奇怪，色相规范的单位是角度，从 0° 到 360°，而且 0° 显然等于 360°，就是#FF0000。为了防止颜色重叠，色相我只取前 0.8 的部分，这样差不多到紫色稍微过一点，比较合适。

参考了(2)的介绍，我自己实现了 HSL2RGB，因为之前 gist 上的 js 代码似乎有很大的问题。但其中计算 X 的里面，需要用到浮点数取模，还好我知道fmod。不过整个函数我写错了好几个地方，因为公式有点复杂，而且轻易还看不出有没有错，只好测试几个数据调试……

代码大概长这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static void hsl2rgb(double h, double s, double l)
{
	h *= 360; // convert to degree
	double c = (1 - fabs(2 * l - 1)) * s;
	double x = c * (1 - fabs(fmod(h / 60, 2) - 1));
	double m = l - c / 2;
	double r, g, b;
	switch ((int)(h / 60))
	{
	case 0:
		r = c; g = x; b = 0;
		break;
	// case 1..5:
	...
	}
	...
}

引入 Windows 控件

我非常想有一个好的用户界面来调整演示（动画）速度，有两种选择：一种是自己用类似 imgui 的方式来实现，捕捉各种鼠标事件，但显然非常麻烦，而且会产生大量潜在 bug；另一种是直接用 Win32 Trackbar，非常方便，但和 imgui 集成有很大的困难。我最终决定还是用 Windows 控件省事。

Microsoft Docs 真的非常详细，但要求读者有一定的基础，而我并没有多少 Win32 编程的经验，于是磕磕绊绊。创建滑动条可以直接抄代码，后面就比较麻烦了。我先后遇到了消息响应、标签提示、闪烁、调节背景色、吞焦点导致 imgui 的快捷键失效等一系列问题。

  • 当滑动条移动的时候怎么更新演示速度呢？查了半天，得改窗体的消息响应（这个写在 graphics.c 中，于是接下来我改了很多图形库的代码），处理WM_HSCROLL事件。这个事件还不会返回当前滑动条的位置，还需要发送TBM_GETPOS消息请求。然后，我不希望用户还没松开鼠标就改变演示速度，这个只要在TB_ENDTRACK时再更新演示速度即可。
  • 由于我采用了非线性速度调节，即创建了一个数组来映射定时器时间间隔，需要提示用户当前选择的速度对应的时间间隔。这个我非常想用内置的Hint，但怎么也实现不了，只能显示数组下标……最终我决定直接在滑动条旁边放一个Label来显示。
  • 闪烁问题显然是 libgraphics 或 imgui 引起的，仔细检查发现是DisplayClear的锅，这玩意儿会强制所有区域重绘。于是解决方法很简单，把控件所在的矩形区域挖掉，不要强制重绘就好了，在窗体创建的时候绘制一次就好了。
  • 滑动条的背景色不是白色，在白色背景的窗体上显得很突兀。要是一般的 UI 设计方案，只要改一下类似BackgroundColor就好了的事情，底层就很麻烦。我没想到需要在窗体处理WM_CTLCOLORSTATIC事件，返回一个白色的HBRUSH。
  • 最后好不容易滑动条终于融入了窗体，突然发现拖动滑动条之后，菜单的快捷键失效了！所幸我还知道 Win32 焦点那套东西，即在窗体上按 Tab 可以切换焦点，到达不同的控件。然而这个窗口上只有一个滑动条控件，菜单根本不是控件，事件完全由窗体来处理！那么解决思路也很简单，把焦点还给窗体即可，只要一个SetFocus。
  • 可是还是有一个缺点，在鼠标拖动滑动条时它还是会获得焦点，同时外面出现了虚线框来表示它具有焦点，这就显得特别丑陋和突兀。查到需要发送WM_CHANGEUISTATE消息到滑动条，参数是UISF_HIDEFOCUS……

您可以感受一下 Win32 的代码（我甚至还学到了原来在 case 里面加大括号就可以定义变量）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
hwndTrack = CreateWindowEx( 
	0,                               // no extended styles 
	TRACKBAR_CLASS,                  // class name 
	"Trackbar Control",              // title (caption) 
	WS_CHILD | 
	WS_VISIBLE | 
	TBS_AUTOTICKS,            // style 
	x * GetXResolution(),
	(winHeight - y) * GetYResolution() - 30,           // position 
	TrackbarWidth * GetXResolution(),
	30,                         // size 
	hwndDlg,                         // parent window 
	NULL,                     // control identifier 
	NULL,                         // instance 
	NULL                             // no WM_CREATE parameter 
	); 

SendMessage(hwndTrack, TBM_SETRANGE, 
	(WPARAM) TRUE,                   // redraw flag 
	(LPARAM) MAKELONG(iMin, iMax));  // min. & max. positions
	
SendMessage(hwndTrack, TBM_SETPAGESIZE, 
	0, (LPARAM) 4);                  // new page size 
	
SendMessage(hwndTrack, TBM_SETPOS, 
	(WPARAM) TRUE,                   // redraw flag 
	(LPARAM) DefInterval); 

//    SetFocus(hwndTrack); 
SendMessage(hwndTrack, WM_CHANGEUISTATE,
	MAKEWPARAM(UIS_SET, UISF_HIDEFOCUS), // hide focus style
	0);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
case WM_HSCROLL:
	dwPos = SendMessage(hwndTrack, TBM_GETPOS, 0, 0);
	ctrl.interval = intervals[dwPos];
	redraw();
	if (LOWORD(wParam) == TB_ENDTRACK)
	{
		SetFocus(graphicsWindow);
		if (ctrl.playing)
		{
			cancelTimer(0);
			startTimer(0, ctrl.interval);
		}
	}
	return 0;

case WM_CTLCOLORSTATIC:
{
	HDC hdcStatic = (HDC) wParam;
	SetTextColor(hdcStatic, RGB(0,0,0));
	SetBkColor(hdcStatic, RGB(255,255,255));
	static HBRUSH hbrBkgnd;
	if (hbrBkgnd == NULL)
	{
		hbrBkgnd = CreateSolidBrush(RGB(255,255,255));
	}
	return (INT_PTR)hbrBkgnd;
}

排序可视化思路

最后聊一下可视化的思路，最简单的方法是直接开个线程执行标准排序，做完一步sleep一段时间，但这样不能实现单步后退。基于非多线程的实现，即仅依靠定时器，我认为有三种实现路线：

  1. 不需要预处理，只保存当前状态，这样应该不能做到单步后退（应该吧），而且递归转非递归实现也很复杂（最难）
  2. 需要预处理，生成所有帧，但只保存帧间变化的部分，单帧的空间与数据规模无关，节省空间（较难）
  3. 需要预处理，生成所有帧，每帧保存所有数据和颜色，单帧的空间与数据规模成正比（较容易）

我一开始就排除了路线 1，因为单步后退是(2)的基本功能，但很多人可能打算这么实现，那我劝他们干脆写多线程，会更容易。而路线 2 更具有挑战性，于是我就开始这么写。不过我还是偷了一点懒，实现了的相当于路线 2-，即虽然帧间变化内部数据是常数复杂度，但前端直接重绘所有数据，复杂度是线性的。于是在超大规模，比如$N=5,000$的时候效率低下，显得非常卡。但一般排序可视化也不会用到那么大的数据规模吧。

P.S. 实际上路线 1 就类似状态机，像是现在在学的硬件编程的感觉。

聊聊汇编大作业

啊，大程一下子写了那么多，那今天就主要聊技术了。听说几位朋友还没写过汇编大作业，也就是十六进制文件查看器，我来聊聊我实现中的一些尝试（和具体实现无关）。首先我给自己定了比较高的目标，不仅要实现所有功能，而且有以下几个原则：

  • 只用 8086 / 8088 汇编，不用任何 32 位的指令，以便在原版的 IBM PC 上运行
  • 尽量不用内存来保存变量，尽量全部用寄存器
  • 在此基础上，获得尽可能小的可执行文件，效率尽可能高

可想而知，我就写的挺慢，可能主体写了一天多，优化大小又花了很久，最终成就是：

  • 效率上，连续翻页 16 MB 的文件，bhh 提供的原始 C 代码用时 77 s，我的汇编用时 16 s；值得注意的是，C 代码也是直接写显存的哦
  • 大小上，C 代码直接用 Turbo C 编译为 9.9 KB，我的汇编从最初的 EXE 版本 2 KB+ 压缩到 COM 版本的 988 字节

效率上，汇编显然有优势，尤其是做了大量寄存器变量优化的情况下。而大小上，我主要采用了以下策略：

  • 把 mov ax, 0 写成 xor ax, ax，即不要直接对 16 位寄存器赋 0，这样可以从 3 字节减少到 2 字节
  • masm 默认 jmp 是 16 位的，如果实际偏移很小，就会插入一个 nop，浪费空间。这样直接找到 nop，把前面的 jmp dest 改成 jmp short dest，就可以从 3 字节减少到 2 字节啦
  • 将 EXE 转为 COM，可以节省大约 0.5 KB 的 EXE 文件头（P.S. MZ 文件头默认就是 200h 字节）
  • 将空白的静态数据转为堆栈分配的动态数据，节省上百字节

可见前两种策略只是使程序简洁，压缩作用不大，后两种策略对中等规模的程序十分有效。

冰火结尾&预告

基本没有剧透，因为您如果没看过原著大概是看不懂的

“A wolf on four legs, or two?”

“Two,” said Meera. “The she-wolf laid into the squires with a tourney sword, scattering them all. The crannogman was bruised and bloodied, so she took him back to her lair to clean his cuts and bind them up with linen. There he met her pack brothers: the wild wolf who led them, the quiet wolf beside him, and the pup who was youngest of the four.

“That evening there was to be a feast in Harrenhal, to mark the opening of the tourney, and the she-wolf insisted that the lad attend. He was of high birth, with as much a right to a place on the bench as any other man. She was not easy to refuse, this wolf maid, so he let the young pup find him garb suitable to a king’s feast, and went up to the great castle.

“Under Harren’s roof he ate and drank with the wolves, and many of their sworn swords besides, barrowdown men and moose and bears and mermen. The dragon prince sang a song so sad it made the wolf maid sniffle, but when her pup brother teased her for crying she poured wine over his head. A black brother spoke, asking the knights to join the Night’s Watch. The storm lord drank down the knight of skulls and kisses in a wine-cup war. The crannogman saw a maid with laughing purple eyes dance with a white sword, a red snake, and the lord of griffins, and lastly with the quiet wolf . . . but only after the wild wolf spoke to her on behalf of a brother too shy to leave his bench.

Meera to BranBran II ASOS

这段摘自布兰北上长城途中，黎德(Reed)姐弟给布兰讲赫伦堡比武大会，神秘骑士的故事。这是我很喜欢的一个桥段，因为里面的人物全部以动物和事物命名，没有给出真名，但读者完全可以推测出所有人的身份。

The one-eared black tom arched his back and hissed at her.

Arya padded down the alley, balanced lightly on the balls of her bare feet, listening to the flutter of her heart, breathing slow deep breaths. Quiet as a shadow, she told herself, light as a feather. The tomcat watched her come, his eyes wary.

Catching cats was hard. Her hands were covered with half-healed scratches, and both knees were scabbed over where she had scraped them raw in tumbles. At first even the cook’s huge fat kitchen cat had been able to elude her, but Syrio had kept her at it day and night. When she’d run to him with her hands bleeding, he had said, “So slow? Be quicker, girl. Your enemies will give you more than scratches.” He had dabbed her wounds with Myrish fire, which burned so bad she had had to bite her lip to keep from screaming. Then he sent her out after more cats.

The Red Keep was full of cats: lazy old cats dozing in the sun, cold-eyed mousers twitching their tails, quick little kittens with claws like needles, ladies’ cats all combed and trusting, ragged shadows prowling the midden heaps. One by one Arya had chased them down and snatched them up and brought them proudly to Syrio Forel … all but this one, this one-eared black devil of a tomcat. “That’s the real king of this castle right there,” one of the gold cloaks had told her. “Older than sin and twice as mean. One time, the king was feasting the queen’s father, and that black bastard hopped up on the table and snatched a roast quail right out of Lord Tywin’s fingers. Robert laughed so hard he like to burst. You stay away from that one, child.”

Arya Catching CatArya III AGOT

昨天讲了不少艾莉亚，于是我也放一段抓猫的场景。结合后文可知，这只黑猫可不一般。（P.S. 理论分析认为它可能就是雷妮丝公主的黑猫贝勒里恩，后来珊莎也遇到过）

还有好多内容没分享，包括考古、《猎魔人》《黑暗物质》、玄学理论等等，敬请期待。

相关链接

  1. https://visualgo.net/en/sorting
  2. https://www.rapidtables.com/convert/color/hsl-to-rgb.html