+/***************************************************************************
+ * 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