-/***************************************************************************
- * libdisorder: A Library for Measuring Byte Stream Entropy
- * Copyright (C) 2010 Michael E. Locasto
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the:
- * Free Software Foundation, Inc.
- * 59 Temple Place, Suite 330
- * Boston, MA 02111-1307 USA
- *
- * $Id$
- **************************************************************************/
-
-#include <math.h> //for log2()
-#include <stdio.h> //for NULL
-#include "disorder.h"
-
-#if defined(__FreeBSD__)
-#define log2(x) (log((x)) * (1./M_LN2))
-#endif
-
-/** Frequecies for each byte */
-static int m_token_freqs[LIBDO_MAX_BYTES]; //frequency of each token in sample
-static float m_token_probs[LIBDO_MAX_BYTES]; //P(each token appearing)
-static int m_num_tokens = 0; //actual number of `seen' tokens, max 256
-static float m_maxent = 0.0;
-static float m_ratio = 0.0;
-static int LIBDISORDER_INITIALIZED = 0;
-
-static void
-initialize_lib()
-{
- int i = 0;
- if(1==LIBDISORDER_INITIALIZED)
- return;
-
- m_num_tokens = 0;
-
- for(i=0;i<LIBDO_MAX_BYTES;i++)
- {
- m_token_freqs[i]=0;
- m_token_probs[i]=0.0;
- }
-
- LIBDISORDER_INITIALIZED = 1;
-}
-
-/**
- * Set m_num_tokens by iterating over m_token_freq[] and maintaining
- * a counter of each position that does not hold the value of zero.
- */
-static void
-count_num_tokens()
-{
- int i = 0;
- int counter = 0;
- for(i=0;i<LIBDO_MAX_BYTES;i++)
- {
- if(0!=m_token_freqs[i])
- {
- counter++;
- }
- }
- m_num_tokens = counter;
- return;
-}
-
-/**
- * Sum frequencies for each token (i.e., byte values 0 through 255)
- * We assume the `length' parameter is correct.
- *
- * This function is available only to functions in this file.
- */
-static void
-get_token_frequencies(char* buf,
- long long length)
-{
- int i=0;
- char* itr=NULL;
- unsigned char c=0;
-
- itr = buf;
-
- //reset number of tokens
- m_num_tokens = 0;
-
- //make sure freqency and probability arrays are cleared
- for(i=0;i<LIBDO_MAX_BYTES;i++)
- {
- m_token_freqs[i] = 0;
- m_token_probs[i] = 0.0;
- }
-
- for(i=0;i<length;i++)
- {
- c = (unsigned char)*itr;
- //assert(0<=c<LIBDO_MAX_BYTES);
- m_token_freqs[c]++;
- itr++;
- }
-}
-
-/**
- * Return entropy (in bits) of this buffer of bytes. We assume that the
- * `length' parameter is correct. This implementation is a translation
- * of the PHP code found here:
- *
- * http://onlamp.com/pub/a/php/2005/01/06/entropy.html
- *
- * with a helpful hint on the `foreach' statement from here:
- *
- * http://php.net/manual/en/control-structures.foreach.php
- */
-float
-shannon_H(char* buf,
- long long length)
-{
- int i = 0;
- float bits = 0.0;
- char* itr=NULL; //values of itr should be zero to 255
- unsigned char token;
- int num_events = 0; //`length' parameter
- float freq = 0.0; //loop variable for holding freq from m_token_freq[]
- float entropy = 0.0; //running entropy sum
-
- if(NULL==buf || 0==length)
- return 0.0;
-
- if(0==LIBDISORDER_INITIALIZED)
- initialize_lib();
-
- itr = buf;
- m_maxent = 0.0;
- m_ratio = 0.0;
- num_events = length;
- get_token_frequencies(itr, num_events); //modifies m_token_freqs[]
- //set m_num_tokens by counting unique m_token_freqs entries
- count_num_tokens();
-
- if(m_num_tokens>LIBDO_MAX_BYTES)
- {
- //report error somehow?
- return 0.0;
- }
-
- //iterate through whole m_token_freq array, but only count
- //spots that have a registered token (i.e., freq>0)
- for(i=0;i<LIBDO_MAX_BYTES;i++)
- {
- if(0!=m_token_freqs[i])
- {
- token = i;
- freq = ((float)m_token_freqs[token]);
- m_token_probs[token] = (freq / ((float)num_events));
- entropy += m_token_probs[token] * log2(m_token_probs[token]);
- }
- }
-
- bits = -1.0 * entropy;
- m_maxent = log2(m_num_tokens);
- m_ratio = bits / m_maxent;
-
- return bits;
-}
-
-int
-get_num_tokens()
-{
- return m_num_tokens;
-}
-
-float
-get_max_entropy()
-{
- return m_maxent;
-}
-
-float
-get_entropy_ratio()
-{
- return m_ratio;
-}
projects / wikiq / commitdiff