高速命中测试

引言

如果您出于任何原因需要编写自定义命中测试，可以使用一种速度极快的方法，该方法可以消除所有比较和边界测试，立即返回一个索引，指示给定坐标集落在哪个区域内。我称之为“映射命中测试”。我是经过多年编码才开发出这种方法的。虽然我是独立想出这个方法的，但很可能它之前已经被使用过了；据我所知，Windows、Linux 和/或其他操作系统可能从一开始就采用了它。我只知道我从未在任何地方看到过这种方法的介绍。该方法与操作系统无关；可以在任何操作系统上实现。

方法

这种方法非常简单，至少在概念上是这样：保留两块内存数组；第一个是水平标志列表，其大小等于显示器的宽度；第二个是显示器的高度。水平数组为监视器上的每一列像素保存一个值。对于 1920 像素宽的监视器，最多保留 1920 个值。垂直数组也类似，代表监视器上的每一行像素。对于 1080 像素高的监视器，垂直数组的最大大小为 1080 个数组元素。这些数字会根据要覆盖的总区域而减小。本文使用的示例有一个 640 x 480 的对话框，作为四个虚拟区域的宿主窗口。由于对话框是模态的，只跟踪其边界内的鼠标移动，因此水平数组是 640 个元素，而垂直数组是 480 个元素。

数组中每个值中的位数决定了可以映射的区域数量。如果您每个条目使用 32 位，最多可以映射 32 个区域。如果您使用 64 位，最多可以映射 64 个区域。如果您需要更大的容量，可以使用 SSE 指令引用数组中的更大值。可以为水平数组和垂直数组使用不同的尺寸——您只需准确地处理您设置的值的大小即可。

我对此方法的实现是一个自定义对话框。在其 44 个控件中有 4 个是虚拟的——Windows 根本不将它们视为控件，因此它们没有固有的鼠标处理。对话框处理程序本身必须检测鼠标在这些区域上的移动并相应地虚拟化处理。这就是映射方法实现的地方。

只有 4 个控件列出，我只需要 4 位来唯一地表示它们。对于每个数组条目，8 位字节是可行的最小大小，因此在这种情况下使用 8 位。如果我想覆盖整个桌面，那么显示器大小将在运行时确定；因此，数组将在那时分配。在我自己的 3840 x 2160 的显示器上，用于整个桌面的数组将是 3840 字节用于水平方向，2160 字节用于垂直方向。但是在这个例子中，我只映射我 640 x 480 对话框内的空间。

使用字节大小的数组条目，我可以标记最多 8 个虚拟区域的位置：每字节 8 位。

我们将使用以下区域 x、y、宽度和高度的任意示例来表示我的四个区域

Area 0: x = 35, y = 027, width = 086, height =  34; flag with bit 0 or a value of 1
Area 1: x = 85, y =  63, width = 113, height = 258; flag with bit 1 or a value of 2
Area 2: x = 17, y = 113, width = 393, height = 198; flag with bit 2 or a value of 4
Area 3: x =  6, y = 145, width = 411, height = 271; flag with bit 3 or a value of 8

上面显示的坐标是相对于对话框窗口的左上角。这些不是屏幕坐标；也不是客户端坐标。它们是相对于对话框窗口的。

下图显示了本文中实际使用的虚拟区域，映射在 640 x 480 的窗口上，如果正确绘制，这将是宿主对话框。

编写映射

对于区域 0，x 坐标是 17，因此找到水平数组中的第 17 个条目。从该位置开始（包括该位置），由于区域的宽度是 227 像素，将 227 个连续的数组条目标记为值 1（设置了位 0），以表示区域 0。使用相同的过程，找到垂直数组中的第 196 个条目，因为区域的 y 坐标是 196。区域的高度是 109 像素，因此垂直数组中从第 196 个条目开始的 109 个条目将被标记为值 1。

此过程对其他三个区域重复进行，依次移动到值 2、4 和 8。每个控件将其标志位左移一位。逻辑 OR 用于应用每个标志值；在开始映射过程之前，两个数组都被清零。值经常会重叠；数组条目可以并且通常会代表多个虚拟区域。这就是为什么使用逻辑 OR 来标记区域位置——以免干扰已标记的任何区域。

这就是映射过程的全部内容。

读取映射

要读取映射，请系好安全带。没有任何比较、测试、if、and 或 but。

鼠标移动消息进入我的对话框回调函数。在对话框初始化期间，我将其屏幕相对坐标加载到静态内存 rect（矩形；左、上、右、下）结构中，这样当对话框未移动时就不需要不断检索它。请记住：此矩形是屏幕相对的，因为当我接收消息时提取鼠标坐标时，这些坐标也是屏幕相对的。

由于映射过程是相对于对话框的，因此如果对话框移动，则不需要重建映射。如果它被调整了大小，则需要重建映射。

对话框窗口的屏幕相对 x 坐标从屏幕相对的鼠标 x 坐标中减去。这使得我正在处理的鼠标 x 坐标相对于对话框窗口——这是我虚拟区域的映射方式。

对鼠标 y 坐标重复此过程，从屏幕相对的鼠标 y 坐标中减去对话框窗口的屏幕相对 y 坐标。现在我有了相对于对话框左上角的鼠标 x 和鼠标 y，这与用于创建鼠标映射的坐标系统相匹配。

假设收到一条消息，转换后鼠标 x 坐标为 106。结果发现，第 106 个水平数组元素（参见上图）将被设置为 0x03 或 00000011b，因为区域 0 和 1 跨越了该像素列。

发送到我的对话框处理程序的鼠标 y 坐标是 89。区域 1，由 0x02 或 00000010b 标记，通过读取垂直数组的第 89 个元素来检索。

水平值为 0x03。垂直值为 0x02。将两者进行逻辑 AND。任何在水平和垂直方向上都不存在的标志值都将被归零。在此示例中，逻辑 AND 的结果将是 0x03 AND 0x02 = 0x02。这是位 1，即区域 1。区域的索引是在逻辑 AND 之后剩余的位。

您可能有重叠的区域；即，一个虚拟滚动条出现在一个客户端区域内。我按 Z 顺序应用标志来处理这类情况。Z 顺序的底部——在这个例子中是客户端区域——比滚动条的位索引更低，滚动条在 Z 顺序中更高。作为任意示例，客户端区域可能是位索引 2，而滚动条是位索引 3。在水平和垂直数组值进行逻辑 AND 之后，位 2 和位 3 都将被设置。由于我构建的映射过程与我的区域的 Z 顺序相匹配，因此在逻辑 AND 之后，我总是想要最高的设置位。在这种情况下，它是位 3。（Intel 架构提供了 BSR 或位扫描反向指令来识别最高的设置位——使用内在函数将使架构无关紧要。）因此区域 3——因为位 3 是逻辑 AND 之后最高的设置位——将代表滚动条，并且会知道鼠标光标在区域 3 上。

总而言之，这就是整个过程。

杂项

对于 16 位条目，将 x 和/或 y 坐标向左移位 1 位，这相当于每行/列像素乘以 2 字节。对于 32 位条目，向左移位 2 位，相当于每行/列像素乘以 4 字节。依此类推。

该过程提供 100% 的准确性，并且几乎可以即时确定给定的 x, y 坐标对所在的虚拟区域，无需搜索、比较或 if 语句。在矩形之后接矩形的内部没有边界检查，这会降低性能。在我自己的汇编代码中，在 Intel 架构上，该过程涉及四个 ASM 指令：加载 X 数组值，加载 Y 数组值，AND，然后 BSR。

这是一个非常优雅的系统，在开发过程中需要一些耐心和大量的微调才能让一切都对齐并正常工作。但一旦到位，命中测试过程就会变得如此之快，以至于它对 CPU 的负担微乎其微。我在多个应用程序中使用了这个过程；它效果非常好，以至于在我转向其他任务时很快就被遗忘了。

在当今的系统上，我为我的映射数组使用的 6,000 字节甚至不值得一提。其中一部分本来就会被缓慢而笨拙地进行边界检查所需的代码占用。如果您想用这个过程映射多达 64 个唯一区域，这个值将增加 8 倍，达到 48,000 字节的内存。在我看来，考虑到提供的性能提升（请记住，我自己的 ASM 应用程序非常非常小），这仍然在“谁在乎？”的范围内。

请记住，如果您打算使用此过程映射整个窗口，请将窗口边框（用于拖动）保留在最低的标志值；然后是上面的标题，然后是标题按钮和系统菜单图标，最后是其余元素。客户端区域作为一个整体使用的标志值低于出现在客户端区域内的区域。

我从未遇到过以这种方式映射整个窗口的问题。只要在分配标志值时考虑到 Z 顺序，该系统就能非常好地工作，实际上它回归了古老的权衡：更高的性能以更高的内存使用和更长的开发时间为代价。