Assembly：数组中整数的出现

Question

我正在用汇编程序编写程序，以计算并返回整数在数组中出现的次数。我目前有以下代码，可让我用随机整数填充数组。我正在努力的是如何实现一个计数器，该计数器将在数组的索引处存储每次出现的整数。例如，如果随机数组为[3,4,3,3,4,5,7,8]，我想让我的count数组保持[3，2，1，1，1，1]，因为（三个3，两个4等）。

我将随机数的范围固定为3/8，所以我知道它们会在此范围内。我目前的想法是将每个数字与3-8相加，然后分别增加我的count数组。我主要的理解不足是如何增加数组的特定索引。这段代码是我如何生成随机整数数组的方法，以了解如何开始计算整数出现的次数，但是我不知道我是否朝着正确的方向前进。有什么建议吗？

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  esi, [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 [esi + 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   esi                  ; restore call-preserved regs
    pop   ebp                  ; including tearing down the stack frame
    ret
我假设UPPER和LOWER是像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），则您有一个固定长度的数组，可以容纳您的计数：