1 /*
2 * HT Editor
3 * tools.cc
4 *
5 * Copyright (C) 1999-2002 Sebastian Biallas (sb@biallas.net)
6 *
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License version 2 as
9 * published by the Free Software Foundation.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 */
20
21 #include "tools.h"
22
23 #include "data.h"
24 #include "htdebug.h"
25 #include <stdlib.h>
26 #include <stdio.h>
27 #include <string.h>
28 #include <math.h>
29
delinearize(uint32 d)30 uint32 delinearize(uint32 d)
31 {
32 return d*0x8088405+1; /* there's magic in here... */
33 }
34
delinearize64(uint64 d)35 uint64 delinearize64(uint64 d)
36 {
37 return (uint64(delinearize(d))<<32)| delinearize(d>>32); /* there's less magic in here... */
38 }
39
compare_keys_uint_delinear(Object * key_a,Object * key_b)40 int compare_keys_uint_delinear(Object *key_a, Object *key_b)
41 {
42 uint a = delinearize(((UInt*)key_a)->value);
43 uint b = delinearize(((UInt*)key_b)->value);
44 if (a>b) return 1; else if (a<b) return -1;
45 return 0;
46 }
47
random_permutation(int max)48 int *random_permutation(int max)
49 {
50 if (!max) return NULL;
51 int *table= ht_malloc(max * sizeof(int));
52 int i,j,k,l,m;
53 for (i=0; i<max; i++) table[i] = i;
54 for (i=0; i<max; i++) {
55 k=rand()%(max);
56 l=rand()%(max);
57 m=rand()%(max);
58 j=table[k];
59 table[k]=table[l];
60 table[l]=j;
61 j=table[i];
62 table[i]=table[m];
63 table[m]=j;
64 }
65 return table;
66 }
67
68 /*
69 * entropy shit
70 */
71 #define LN2 0.693147180559945309417232121458177
72
calc_entropy(byte * buf,int size)73 double calc_entropy(byte *buf, int size)
74 {
75 int p[256];
76 if (!size) return 0.0;
77 memset(p, 0, sizeof p);
78 for (int i=0; i<size; i++) {
79 p[*buf]++;
80 buf++;
81 }
82 double result = 0.0;
83 for (int i=0; i<256; i++) {
84 if (p[i]) {
85 double pi = p[i];
86 pi /= size;
87 result += pi * log(pi) / LN2;
88 }
89 }
90 return -result;
91 }
92
93 /*
94 * buffer size must be 64 bytes
95 * return value will be in range from 0 to 100
96 */
calc_entropy2(byte * buf,int size)97 int calc_entropy2(byte *buf, int size)
98 {
99 int p[256];
100 int result = 0;
101 if (size<3) return 0;
102 memset(p, 0, sizeof p);
103 // pass1
104 byte *b = buf;
105 for (int i=0; i < size; i++) {
106 if (p[*b]++ == 0) {
107 result ++;
108 }
109 b++;
110 }
111 memset(p, 0, sizeof p);
112 b = buf;
113 // pass2
114 size--;
115 for (int i=0; i < size; i++) {
116 int d = b[0]-b[1];
117 if (d<0) d = -d;
118 if (p[d]++ == 0) {
119 result ++;
120 }
121 b++;
122 }
123 memset(p, 0, sizeof p);
124 b = buf;
125 // pass3
126 size--;
127 for (int i=0; i < size; i++) {
128 int d = b[0]-b[1];
129 int e = b[1]-b[2];
130 if (d<0) d = -d;
131 if (e<0) e = -e;
132 d = d-e;
133 if (d<0) d = -d;
134 if (p[d]++ == 0) {
135 result ++;
136 }
137 b++;
138 }
139 return (result-3)*100/(size*3+3);
140 }
141
142 /*
143 * "out of memory" - handlers
144 */
145
out_of_memory(int size)146 int out_of_memory(int size)
147 {
148 printf("Out of memory.");
149 exit(1);
150 return OUT_OF_MEMORY_FAIL;
151 }
152
153 int (*out_of_memory_func)(int size)=&out_of_memory;
154
smalloc(size_t size)155 void *smalloc(size_t size)
156 {
157 void *p;
158 retry:
159 if ((p=malloc(size))) return p;
160 switch (out_of_memory_func(size)) {
161 case OUT_OF_MEMORY_IGNORE:
162 return NULL;
163 case OUT_OF_MEMORY_RETRY:
164 goto retry;
165 default:
166 exit(666);
167 }
168 }
169
smalloc0(size_t size)170 void *smalloc0(size_t size)
171 {
172 void *p;
173 retry0:
174 if ((p=malloc(size))) return memset(p, 0, size);
175 switch (out_of_memory_func(size)) {
176 case OUT_OF_MEMORY_IGNORE:
177 return NULL;
178 case OUT_OF_MEMORY_RETRY:
179 goto retry0;
180 default:
181 exit(666);
182 }
183 }
184
185