汇编:数组中整数的出现

Question

我正在masm程序集中编写一个程序来计数和返回数组中整数出现的次数。我目前有以下代码，允许我使用随机整数填充数组。我所挣扎的是如何实现一个计数器，该计数器将在数组中的索引处存储每一个整数的出现。例如，如果随机数组是3,4, 3，3,4,5,7,8，我希望我的计数数组容纳3，2，1，1，1，1，因为有(3，3，2，4，等等)。

我有固定在3/8的随机数的界，所以我知道它们将在这个范围内。我目前的想法是将每个数字与添加的3-8进行比较，并分别增加计数数组。我主要缺乏理解的是如何增加数组的特定索引。这段代码是我如何生成一个随机整数数组的，我知道如何开始计数整数的出现，但我不知道我是否在朝着正确的方向前进。有什么建议吗？

push ebp
mov  ebp, esp
mov  esi, [ebp + 16]    ; @ holds array to store count of integer occurances
mov  edi, [ebp + 12]  ; @ holds array to be populated with random ints
mov  ecx, [ebp + 8]   ; value of request in ecx


MakeArray:              
    mov     eax, UPPER          ; upper boundary for random num in array
    sub     eax, LOWER          ; lower boundary for random num in array
    inc     eax             
    call    RandomRange
    add     eax, LOWER
    cmp     eax, 3          ; Where I start to compare the random numbers added
    je      inc_3           ; current thought is it cmp to each num 3-8
    mov     [edi], eax  ; put random number in array
    add     edi, 4      ; holds address of current element, moves to next element
    loop    fillArrLoop

inc_3:          ; if random num == 3
    inc     esi         ; holds address of count_array, increments count_array[0] to 1?
    mov     [edi], eax  ; put random number in array to be displayed
    add     edi, 4      ; holds address of current element, moves to next element
    loop    MakeArray

Answer 1

，我目前的想法是将每个数字与添加的3-8进行比较。

不，你把事情搞得太复杂了。您不希望对j (计数索引)进行线性搜索，因此arr[i] == j只需使用j = arr[i]。

做直方图的标准方法是++counts[ arr[i] ]. 在您的示例中，您知道可能的值是3.8，因此您可以使用arr[i] - 3将数组值映射到计数桶，因此您将对counts[0..5]进行操作。给定寄存器中的元素值，具有缩放索引寻址模式的内存目的地add 指令可以在一个x86指令中完成这一任务。

如果可能的值不是连续的，则通常使用哈希表来映射值以计数桶。您可以把这个简单的例子看作是允许一个琐碎的散列函数。

由于您正在生成随机数来填充arr[i]和直方图，您可以组合这两个任务，而不是减去3，只是还没有添加它。

; inputs: unsigned len, int *values, int *counts
; outputs: values[0..len-1] filled with random numbers, counts[] incremented
; clobbers: EAX, ECX, EDX  (not the other registers)
fill_array_and_counts:
    push ebp
    mov  ebp, esp

    push esi        ; Save/restore the caller's ESI.
 ;; Irvine32 functions like RandomRange are special and don't clobber EAX, ECX, or EDX except as return values,
 ;; so we can use EDX and ECX even in a loop that makes a function call.

    mov  edi, [ebp + 16]    ; int *counts  ; assumed already zeroed?
    mov  edx, [ebp + 12]    ; int *values  ; output pointers
    mov  ecx, [ebp + 8]     ; size_t length

    MakeArray:                       ; do{
        mov     eax, UPPER - LOWER + 1   ; size of random range, calculated at assemble time
        call    RandomRange                  ; eax = 0 .. eax-1
        add     dword ptr [edi + eax*4], 1   ; ++counts[ randval ]

        add     eax, LOWER               ; map 0..n to LOWER..UPPER
        mov     [edx], eax               ; *values = randval+3
        add     edx, 4                   ; values++

        dec     ecx
        jnz     MakeArray            ; }while(--ecx);

    pop   edi                  ; restore call-preserved regs
    pop   ebp                  ; including tearing down the stack frame
    ret

如果调用方没有为您设置counts数组的零点，那么您应该自己完成这一操作，也许使用rep stosd将EAX=0作为ECX元素的memset，然后从堆栈args中重新加载EDI和ECX。

我假设上下是集合时间常数，比如UPPER = 8或LOWER equ 3，因为它们都是大写名称，而它们不是函数args。如果是这样的话，那么没有必要在运行时进行计算，只需让汇编程序为您计算UPPER - LOWER + 1。

我避免了loop指令because it's slow，也没有做其他简单指令不能做的事情。

只有几个桶的直方图的一个标准性能技巧是有多个计数数组并展开它们：Methods to vectorise histogram in SIMD?。这隐藏了存储/重新加载的延迟，当同一计数器需要在一行中增加几次时。但是，随机值通常会避免相同值的长时间运行，因此避免了最坏的性能。

对于大型数组，可能会从AVX2获得一些好处，因为只有6个可能的桶：Micro Optimization of a 4-bucket histogram of a large array or list。(如果愿意，可以用AVX2 xorshift128+ PRNG在SIMD向量中生成随机数。)

Answer 2

如果您的范围是固定的(3-8)，则有一个固定长度的数组，可以保存计数：

(index0:Count of 3),(index1:Count of 4)..(index5:Count of 8s)

一旦从随机数组中获得了一个元素，您只需接受该元素并通过一个开关：

cmp 3, [element]
jne compare4
mov ebx, [countsArrayAddress]     ; Can replace [countsArrayAddress] with  [ebp + 16]
add ebx, 0                        ; First index, can comment out this line
mov ecx, [ebx]
add ecx, 1                        ; Increment count
mov [ebx], ecx                    ; Count at the zeroth offset is now incremented
compare4:
cmp 4, [element]
jne compare5
mov ebx, [countsArrayAddress]
add ebx, 4                         ; Second index (1*4)
mov ecx, [ebx]
add ecx, 1
mov [ebx], ecx
...

你是这个意思吗？我来自于使用fasm语法，但它看起来非常相似。上面的块有一点未优化，但请考虑这说明了如何构建计数数组。数组有一个固定长度，必须在堆栈上(子rsp为正确的数量)或堆上，即使用heapalloc/malloc调用来分配。(编辑，见您正在使用32位寄存器)