Compiler · Sarvik

Run it

Shannon entropy in one pass: count each byte value, then sum −p·log₂p over the buckets. Edit a string and run it again. One repeated byte carries no information, two symbols in equal measure carry one bit each, eight distinct bytes carry three.

editable · Ctrl Enter runs it

#include <cmath>
#include <cstdio>
#include <string_view>

// Shannon entropy in bits per byte: one counting pass, then sum -p log2 p.
double entropy(std::string_view s) {
    unsigned long long counts[256] = {};
    for (unsigned char c : s) counts[c]++;
    double h = 0;
    for (auto c : counts)
        if (c) { double p = double(c) / s.size(); h -= p * std::log2(p); }
    return h;
}

int main() {
    for (std::string_view s : {"aaaaaaaa", "abababab", "abcdefgh",
                               "the quick brown fox jumps over the lazy dog"})
        std::printf("%6.3f bits/byte  %.*s\n", entropy(s), int(s.size()), s.data());
}

output x86-64 gcc 14.2 exit 0 open ↗

 0.000 bits/byte  aaaaaaaa
 1.000 bits/byte  abababab
 3.000 bits/byte  abcdefgh
 4.385 bits/byte  the quick brown fox jumps over the lazy dog

fig.01, byte entropy · x86-64 gcc 14.2, -O2 -std=c++20

Read the machine code

The same counting loop compiled twice. On x86-64 it is five instructions: movzx the byte, then add straight into memory. For WebAssembly, clang unrolls it by four and, on a stack machine, spells every increment out as i64.load, i64.add, i64.store. Edit the loop and both targets recompile.

editable · Ctrl Enter runs it

// The counting loop from fig.01: one increment per byte.
void feed(unsigned long long* counts, const unsigned char* p, unsigned n) {
    for (unsigned i = 0; i < n; i++) counts[p[i]]++;
}

x86-64 gcc 14.2 -O3 open ↗

feed(unsigned long long*, unsigned char const*, unsigned int):
        test    edx, edx
        je      .L1
        mov     edx, edx
        add     rdx, rsi
.L3:
        movzx   eax, BYTE PTR [rsi]
        add     rsi, 1
        add     QWORD PTR [rdi+rax*8], 1
        cmp     rsi, rdx
        jne     .L3
.L1:
        ret

WebAssembly clang (trunk) -O3 open ↗

feed(unsigned long long*, unsigned char const*, unsigned int):
        block           
        local.get       2
        i32.eqz
        br_if           0
        local.get       2
        i32.const       3
        i32.and 
        local.set       3
        i32.const       0
        local.set       4
        block           
        local.get       2
        i32.const       4
        i32.lt_u
        br_if           0
        local.get       2
        i32.const       -4
        i32.and 
        local.set       5
        i32.const       0
        local.set       4
        loop            
        local.get       0
        local.get       1
        local.get       4
        i32.add 
        local.tee       2
        i32.load8_u     0
        i32.const       3
        i32.shl 
        i32.add 
        local.tee       6
        local.get       6
        i64.load        0
        i64.const       1
        i64.add 
        i64.store       0
        local.get       0
        local.get       2
        i32.const       1
        i32.add 
        i32.load8_u     0
        i32.const       3
        i32.shl 
        i32.add 
        local.tee       6
        local.get       6
        i64.load        0
        i64.const       1
        i64.add 
        i64.store       0
        local.get       0
        local.get       2
        i32.const       2
        i32.add 
        i32.load8_u     0
        i32.const       3
        i32.shl 
        i32.add 
        local.tee       6
        local.get       6
        i64.load        0
        i64.const       1
        i64.add 
        i64.store       0
        local.get       0
        local.get       2
        i32.const       3
        i32.add 
        i32.load8_u     0
        i32.const       3
        i32.shl 
        i32.add 
        local.tee       2
        local.get       2
        i64.load        0
        i64.const       1
        i64.add 
        i64.store       0
        local.get       5
        local.get       4
        i32.const       4
        i32.add 
        local.tee       4
        i32.ne  
        br_if           0
        end_loop
        local.get       3
        i32.eqz
        br_if           1
        end_block
        local.get       1
        local.get       4
        i32.add 
        local.set       2
        loop            
        local.get       0
        local.get       2
        i32.load8_u     0
        i32.const       3
        i32.shl 
        i32.add 
        local.tee       4
        local.get       4
        i64.load        0
        i64.const       1
        i64.add 
        i64.store       0
        local.get       2
        i32.const       1
        i32.add 
        local.set       2
        local.get       3
        i32.const       -1
        i32.add 
        local.tee       3
        br_if           0
        end_loop
        end_block
        end_function

fig.02, the histogram inner loop · x86-64 gcc 14.2 vs. WebAssembly clang, both -O3

Code runs on Compiler Explorer, requested from your browser only when you press Run. Results shown before that were compiled when this page was built.