Calculate entropy of a file
Question: I have tried to search this function for over two hours from google, forums,
wikipedia and many, many forums but I couldn't find it. How I can do this? I
tried the following but it didn't work.

    
    
     #include <stdio.h>
     #include <stdlib.h>
     #include <math.h>
     #include <string.h>
     #include <stdint.h>
    
     static unsigned int mylog2 (unsigned int val) {
     unsigned int ret = -1;
     while (val != 0) {
        val >>= 1;
        ret++;
    }
    return ret;
    }
    
    int main(int argc, char **argv)
    {
    FILE            *pFile;
    int             i;              // various loop index
    int             j;              // filename loop index
    int             n;              // Bytes read by fread;
    int             size;           // Filesize
    float           entropy;
    float           temp;           // temp value used in entropy calculation
    long            alphabet[256];
    unsigned char   buffer[1024];
    
    
    /* do this for all files */
    for(j = 1; j < argc; j++)
    {
        /* initialize all values */
        size = 0;
        entropy = 0.0;
        memset(alphabet, 0, sizeof(long) * 256);
    
        pFile = fopen(argv[j], "rb");
        if(pFile == NULL)
        {
            printf("Failed to open `%s`\n", argv[j]);
            continue;
        }
    
        /* Read the whole file in parts of 1024 */
        while((n = fread(buffer, 1, 1024, pFile)) != 0)
        {
            /* Add the buffer to the alphabet */
            for (i = 0; i < n; i++)
            {
                alphabet[(int) buffer[i]]++;
                size++;
            }
        }
        fclose(pFile);
    
        /* entropy calculation */
        for (i = 0; i < 256; i++)
        {
            if (alphabet[i] != 0)
            {
                temp = (float) alphabet[i] / (float) size;
                entropy += -temp * mylog2(temp);
            }
        }
        printf("%02.5f [ %02.5f ]\t%s\n", entropy, entropy / 8, argv[j]);
    }
    return 0;
    }
    

I know I am doing it wrong. In python it's seems to be a lot easier, in python
it is:

    
    
       import sys
    import math
    
    if len(sys.argv) != 2:
        print "Usage: file_entropy.py [path]filename"
        sys.exit()
    
    # read the whole file into a byte array
    f = open(sys.argv[1], "rb")
    byteArr = map(ord, f.read())
    f.close()
    fileSize = len(byteArr)
    print 'File size in bytes:'
    print fileSize
    print
    
    # calculate the frequency of each byte value in the file
    freqList = []
    for b in range(256):
        ctr = 0
        for byte in byteArr:
            if byte == b:
                ctr += 1
        freqList.append(float(ctr) / fileSize)
    # print 'Frequencies of each byte-character:'
    # print freqList
    # print
    
    # Shannon entropy
    ent = 0.0
    for freq in freqList:
        if freq > 0:
            ent = ent + freq * math.log(freq, 2)
    ent = -ent
    print 'Shannon entropy (min bits per byte-character):'
    print ent
    print
    print 'Min possible file size assuming max theoretical compression efficiency:'
    print (ent * fileSize), 'in bits'
    print (ent * fileSize) / 8, 'in bytes'
    
    ###  Modifications to file_entropy.py to create the Histogram start here ###
    ### by Ken Hartman  www.KennethGHartman.com
    
    import numpy as np
    import matplotlib.pyplot as plt
    
    N = len(freqList)
    
    ind = np.arange(N)  # the x locations for the groups
    width = 1.00        # the width of the bars
    
    #fig = plt.figure()
    fig = plt.figure(figsize=(11,5),dpi=100)
    ax = fig.add_subplot(111)
    rects1 = ax.bar(ind, freqList, width)
    ax.set_autoscalex_on(False)
    ax.set_xlim([0,255])
    
    ax.set_ylabel('Frequency')
    ax.set_xlabel('Byte')
    ax.set_title('Frequency of Bytes 0 to 255\nFILENAME: ' + sys.argv[1])
    
    plt.show()
    

How to achieve the same in C++ ? Hopefully somebody answers factually.


Answer: The Shannon entropy is `H= -1*sum(p_i*log(p_i))` where **p_i** is the
_frequency of each symbol i (the sum) and the result is in bits per symbol if
the log base is 2_ , **"nats"** _if the log base is n_. But it changes if you
change how you express the data, i.e. if the same data is expressed as bit,
bytes, etc. So you can **divide by log(n)** where _n is the number of symbols
available (2 for binary, 256 for bytes) and H will range from 0 to 1 (this is
normalized intensive Shannon entropy)_.

The above entropy is an **"intensive"** form, i.e. per symbol which is
analogous to specific entropy in physics, per kg or per mole. Regular
"extensive" entropy like physics entropy is `S=N*H` where N is the number of
symbols in the file. A little math with the above H gives **normalized
extensive entropy for a file** , where "n" is number of distinct "i" symbols
(2 for binary, 256 for bytes):

    
    
    S=N * H / log(n) = sum(count_i*log(N/count_i))/log(n)
    

For files with equal frequency of each symbol this gives `S=N`. Entropy does
not do any compression on the data and is thereby completely ignorant of any
patterns so 000000111111 has same H and S as 010111101000 (6 1's and 6 0's in
both cases).

