From Lars Roland: Move timestamp_type into libethereal and provide accessor
[obnox/wireshark/wip.git] / epan / int-64bit.c
1 /* int-64bit.c
2  * Routines for handling of 64-bit integers
3  * 2001 Ronnie Sahlberg
4  *
5  * $Id: int-64bit.c,v 1.3 2002/08/28 20:40:44 jmayer Exp $
6  *
7  * Ethereal - Network traffic analyzer
8  * By Gerald Combs <gerald@ethereal.com>
9  * Copyright 1998 Gerald Combs
10  *
11  * This program is free software; you can redistribute it and/or
12  * modify it under the terms of the GNU General Public License
13  * as published by the Free Software Foundation; either version 2
14  * of the License, or (at your option) any later version.
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License
22  * along with this program; if not, write to the Free Software
23  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
24  */
25
26 #ifdef HAVE_CONFIG_H
27 # include "config.h"
28 #endif
29
30 #include <string.h>
31 #include "int-64bit.h"
32
33 /* all functions take the 64bit integer parameter as a
34    pointer to a 64bit integer in network order.
35    that is ptr[0] is the most significant byte and
36    ptr[7] is the least significant byte.
37 */
38
39 #define U64STRLEN       21
40
41
42 /* this must be signed. if it is not clear why, please dont
43    modify the functions in this file. it will break.
44 */
45 static const signed char u64val[64][U64STRLEN] =
46 {
47 /* 1  */        { 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
48 /* 2  */        { 2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
49 /* 3  */        { 4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
50 /* 4  */        { 8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
51 /* 5  */        { 6,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
52 /* 6  */        { 2,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
53 /* 7  */        { 4,6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
54 /* 8  */        { 8,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
55 /* 9  */        { 6,5,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
56 /* 10 */        { 2,1,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
57 /* 11 */        { 4,2,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
58 /* 12 */        { 8,4,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
59 /* 13 */        { 6,9,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
60 /* 14 */        { 2,9,1,8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
61 /* 15 */        { 4,8,3,6,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
62 /* 16 */        { 8,6,7,2,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
63 /* 17 */        { 6,3,5,5,6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
64 /* 18 */        { 2,7,0,1,3,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
65 /* 19 */        { 4,4,1,2,6,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
66 /* 20 */        { 8,8,2,4,2,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
67 /* 21 */        { 6,7,5,8,4,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
68 /* 22 */        { 2,5,1,7,9,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
69 /* 23 */        { 4,0,3,4,9,1,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
70 /* 24 */        { 8,0,6,8,8,3,8,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },
71 /* 25 */        { 6,1,2,7,7,7,6,1,0,0,0,0,0,0,0,0,0,0,0,0,0 },
72 /* 26 */        { 2,3,4,4,5,5,3,3,0,0,0,0,0,0,0,0,0,0,0,0,0 },
73 /* 27 */        { 4,6,8,8,0,1,7,6,0,0,0,0,0,0,0,0,0,0,0,0,0 },
74 /* 28 */        { 8,2,7,7,1,2,4,3,1,0,0,0,0,0,0,0,0,0,0,0,0 },
75 /* 29 */        { 6,5,4,5,3,4,8,6,2,0,0,0,0,0,0,0,0,0,0,0,0 },
76 /* 30 */        { 2,1,9,0,7,8,6,3,5,0,0,0,0,0,0,0,0,0,0,0,0 },
77 /* 31 */        { 4,2,8,1,4,7,3,7,0,1,0,0,0,0,0,0,0,0,0,0,0 },
78 /* 32 */        { 8,4,6,3,8,4,7,4,1,2,0,0,0,0,0,0,0,0,0,0,0 },
79 /* 33 */        { 6,9,2,7,6,9,4,9,2,4,0,0,0,0,0,0,0,0,0,0,0 },
80 /* 34 */        { 2,9,5,4,3,9,9,8,5,8,0,0,0,0,0,0,0,0,0,0,0 },
81 /* 35 */        { 4,8,1,9,6,8,9,7,1,7,1,0,0,0,0,0,0,0,0,0,0 },
82 /* 36 */        { 8,6,3,8,3,7,9,5,3,4,3,0,0,0,0,0,0,0,0,0,0 },
83 /* 37 */        { 6,3,7,6,7,4,9,1,7,8,6,0,0,0,0,0,0,0,0,0,0 },
84 /* 38 */        { 2,7,4,3,5,9,8,3,4,7,3,1,0,0,0,0,0,0,0,0,0 },
85 /* 39 */        { 4,4,9,6,0,9,7,7,8,4,7,2,0,0,0,0,0,0,0,0,0 },
86 /* 40 */        { 8,8,8,3,1,8,5,5,7,9,4,5,0,0,0,0,0,0,0,0,0 },
87 /* 41 */        { 6,7,7,7,2,6,1,1,5,9,9,0,1,0,0,0,0,0,0,0,0 },
88 /* 42 */        { 2,5,5,5,5,2,3,2,0,9,9,1,2,0,0,0,0,0,0,0,0 },
89 /* 43 */        { 4,0,1,1,1,5,6,4,0,8,9,3,4,0,0,0,0,0,0,0,0 },
90 /* 44 */        { 8,0,2,2,2,0,3,9,0,6,9,7,8,0,0,0,0,0,0,0,0 },
91 /* 45 */        { 6,1,4,4,4,0,6,8,1,2,9,5,7,1,0,0,0,0,0,0,0 },
92 /* 46 */        { 2,3,8,8,8,0,2,7,3,4,8,1,5,3,0,0,0,0,0,0,0 },
93 /* 47 */        { 4,6,6,7,7,1,4,4,7,8,6,3,0,7,0,0,0,0,0,0,0 },
94 /* 48 */        { 8,2,3,5,5,3,8,8,4,7,3,7,0,4,1,0,0,0,0,0,0 },
95 /* 49 */        { 6,5,6,0,1,7,6,7,9,4,7,4,1,8,2,0,0,0,0,0,0 },
96 /* 50 */        { 2,1,3,1,2,4,3,5,9,9,4,9,2,6,5,0,0,0,0,0,0 },
97 /* 51 */        { 4,2,6,2,4,8,6,0,9,9,9,8,5,2,1,1,0,0,0,0,0 },
98 /* 52 */        { 8,4,2,5,8,6,3,1,8,9,9,7,1,5,2,2,0,0,0,0,0 },
99 /* 53 */        { 6,9,4,0,7,3,7,2,6,9,9,5,3,0,5,4,0,0,0,0,0 },
100 /* 54 */        { 2,9,9,0,4,7,4,5,2,9,9,1,7,0,0,9,0,0,0,0,0 },
101 /* 55 */        { 4,8,9,1,8,4,9,0,5,8,9,3,4,1,0,8,1,0,0,0,0 },
102 /* 56 */        { 8,6,9,3,6,9,8,1,0,7,9,7,8,2,0,6,3,0,0,0,0 },
103 /* 57 */        { 6,3,9,7,2,9,7,3,0,4,9,5,7,5,0,2,7,0,0,0,0 },
104 /* 58 */        { 2,7,8,5,5,8,5,7,0,8,8,1,5,1,1,4,4,1,0,0,0 },
105 /* 59 */        { 4,4,7,1,1,7,1,5,1,6,7,3,0,3,2,8,8,2,0,0,0 },
106 /* 60 */        { 8,8,4,3,2,4,3,0,3,2,5,7,0,6,4,6,7,5,0,0,0 },
107 /* 61 */        { 6,7,9,6,4,8,6,0,6,4,0,5,1,2,9,2,5,1,1,0,0 },
108 /* 62 */        { 2,5,9,3,9,6,3,1,2,9,0,0,3,4,8,5,0,3,2,0,0 },
109 /* 63 */        { 4,0,9,7,8,3,7,2,4,8,1,0,6,8,6,1,1,6,4,0,0 },
110 /* 64 */        { 8,0,8,5,7,7,4,5,8,6,3,0,2,7,3,3,2,2,9,0,0 }
111 };
112
113
114 /* convert an unsigned  64 bit integer into a string
115    it is important that this function is efficient
116    since it will be used for every 64bit integer in
117    any capture.
118    It is much less important that the inverse: atou64
119    be efficient since it is only called when
120    diplayfilters are entered.
121
122    "neg" should be 1 if the number should have a "-" put in
123    front of it.
124 */
125 static char *
126 n64toa(const unsigned char *u64ptr, int neg)
127 {
128         unsigned char acc[U64STRLEN]; /* accumulator */
129         int i,j,k,pos;
130         static char str[U64STRLEN+1]; /* 1 extra for the sign */
131
132         /* clear out the accumulator */
133         for(i=0;i<U64STRLEN-1;i++){
134                 acc[i]=0;
135         }
136
137         pos=0;
138         /* loop over the 8 bytes of the 64bit integer,
139            lsb to msb */
140         for(i=7;i>=0;i--){
141                 /* optimize, most of these bytes will be 0 ?*/
142                 if(u64ptr[i]==0){
143                         pos+=8;
144                 } else {
145                         for(j=0;j<8;j++,pos++){
146                                 if(u64ptr[i]&(1<<j)){
147                                         for(k=0;k<U64STRLEN-1;k++){
148                                                 acc[k]+=u64val[pos][k];
149                                         }
150                                 }
151                         }
152                 }
153                 /* we must handle carries inside this loop
154                    since othevise the signed char in acc will
155                    owerflow/wrap, but we dont need to do it
156                    for every iteration. its enough if we
157                    do it halfway through and at the end
158                    and we will prevent any overflow.
159                 */
160                 if((i%4)==0){
161                         /* handle carries */
162                         for(j=0;j<U64STRLEN-1;j++){
163                                 if(acc[j]>9){
164                                         int x;
165                                         x=acc[j]/10;
166                                         acc[j+1]+=x;
167                                         acc[j]-=x*10;
168                                 }
169                         }
170                 }
171         }
172
173         /* convert to a string */
174         str[U64STRLEN-1+neg]=0;
175         for(i=0;i<U64STRLEN-1;i++){
176                 str[U64STRLEN-2-i+neg]='0'+acc[i];
177         }
178
179         /* skip the initial zeros */
180         for(i=0;i<U64STRLEN-2;i++){
181                 if(str[i+neg]>'0'){
182                         break;
183                 }
184         }
185
186         /* insert the sign */
187         if (neg)
188                 str[i] = '-';
189
190         return str+i;
191 }
192
193 /*
194  * Convert an unsigned 64-bit integer into a string, in decimal.
195  */
196 char *
197 u64toa(const unsigned char *u64ptr)
198 {
199         /*
200          * Just use "n64toa()".
201          */
202         return n64toa(u64ptr, 0);
203 }
204
205 /*
206  * Convert a signed 64-bit integer into a string, in decimal.
207  */
208 char *
209 i64toa(const unsigned char *i64ptr)
210 {
211         unsigned char neg[8];
212         int i;
213         int carry;
214         int byte;
215
216         /*
217          * The bytes of the integer go from msb to lsb, so the
218          * msb is "i64ptr[0]".
219          *
220          * The sign bit, therefore, is "i64ptr[0] & 0x80".
221          */
222         if (i64ptr[0] & 0x80) {
223                 /*
224                  * It's negative - compute the absolute value,
225                  * by taking the two's complement; take the
226                  * one's complement of the low-order byte, add
227                  * 1, take the one's complement of the next byte
228                  * up, add the carry from the previous addition,
229                  * etc.
230                  *
231                  * If it's the maximum negative value, which is
232                  * 0x8000000000000000, this will turn it back
233                  * into 0x8000000000000000, which "n64toa()"
234                  * will handle correctly, reporting the absolute
235                  * value of the maximum negative value;
236                  * thus, we don't have to worry about it.
237                  */
238                 carry = 1;
239                 for (i = 7; i >= 0; i--) {
240                         byte = ((unsigned char)~i64ptr[i]) + carry;
241                         neg[i] = byte;
242                         if (byte & 0x100)
243                                 carry = 1;
244                         else
245                                 carry = 0;
246                 }
247
248                 /*
249                  * Use "n64toa()" on the negative, and tell it to insert
250                  * a "-".
251                  */
252                 return n64toa(neg, 1);
253         } else {
254                 /*
255                  * It's positive, so just use "n64toa()".
256                  */
257                 return n64toa(i64ptr, 0);
258         }
259 }
260
261 /* like memcmp but compares in reverse */
262 static int
263 revcmp(const signed char *s1, const signed char *s2, int len)
264 {
265         int i;
266
267         for(i=len-1;i>=0;i--){
268                 if(s1[i]==s2[i]){
269                         continue;
270                 }
271                 if(s1[i]>s2[i]){
272                         return 1;
273                 } else {
274                         return -1;
275                 }
276         }
277         return 0;
278 }
279
280 /*
281  * Convert a string to an unsigned 64-bit integer.
282  */
283 unsigned char *
284 atou64(const char *u64str, unsigned char *u64int)
285 {
286         signed char res[U64STRLEN]; /* residual */
287         int i,j,len;
288         const char *strp;
289
290         if(!u64str){
291                 return NULL;
292         }
293
294         /* if it is a hex string */
295         if( (u64str[0]=='0')
296         &&  (u64str[1]=='x') ){
297                 return htou64(u64str, u64int);
298         }
299
300         /* verify that the string is ok */
301         for(strp=u64str;*strp;strp++){
302                 if((*strp>='0')&&(*strp<='9')){
303                         continue;
304                 }
305                 return NULL;
306         }
307
308         /* clear the result vector */
309         for(i=0;i<8;i++){
310                 u64int[i]=0;
311         }
312
313         /* clear the residual string and copy the
314            original to it (subtracting '0')
315         */
316         for(i=0;i<U64STRLEN;i++){
317                 res[i]=0;
318         }
319         while(*u64str=='0'){ /* skip initial blanks */
320                 u64str++;
321         }
322         len=strlen(u64str)-1;
323         for(i=0;len>=0;i++,len--){
324                 res[i]=u64str[len]-'0';
325         }
326
327         /* go through all bits and subtract their
328            value */
329         for(i=63;i>=0;i--){
330                 if(revcmp(u64val[i], res, U64STRLEN)<=0){
331                         u64int[7-(i>>3)]|=(1<<(i&0x07));
332                         for(j=0;j<U64STRLEN;j++){
333                                 res[j]-=u64val[i][j];
334                                 /*underflow*/
335                                 if(res[j]<0){
336                                         res[j]+=10;
337                                         res[j+1]-=1;
338                                 }
339                         }
340                 }
341         }
342
343         return u64int;
344 }
345
346 /*
347  * Convert a string to a signed 64-bit integer.
348  */
349 unsigned char *
350 atoi64(const char *i64str, unsigned char *i64int)
351 {
352         int i;
353         int carry;
354         int byte;
355
356         if(!i64str){
357                 return NULL;
358         }
359
360         /*
361          * Does it begin with a minus sign?
362          */
363         if (i64str[0] == '-') {
364                 /*
365                  * Yes - convert the rest of the string to a number...
366                  */
367                 if (atou64(&i64str[1], i64int) == NULL) {
368                         /*
369                          * We failed.
370                          */
371                         return NULL;
372                 }
373
374                 /*
375                  * ...and then take its negative.
376                  */
377                 carry = 1;
378                 for (i = 7; i >= 0; i--) {
379                         byte = ((unsigned char)~i64int[i]) + carry;
380                         i64int[i] = byte;
381                         if (byte & 0x100)
382                                 carry = 1;
383                         else
384                                 carry = 0;
385                 }
386                 return i64int;
387         } else {
388                 /*
389                  * No - just let "atou64()" handle it.
390                  */
391                 return atou64(i64str, i64int);
392         }
393 }
394
395 /*
396  * Convert an unsigned 64-bit integer to a string, in hex.
397  */
398 char *
399 u64toh(const unsigned char *u64ptr)
400 {
401         static char str[19], *strp;
402         static char ntoh[] = {'0','1','2','3','4','5','6','7',
403                 '8','9','a','b','c','d','e','f'};
404         int i;
405
406         str[0]='0';
407         str[1]='x';
408         strp=str+2;
409         for(i=0;i<8;i++){
410                 *strp++ = ntoh[u64ptr[i]>>4];
411                 *strp++ = ntoh[u64ptr[i]&0x0f];
412         }
413         *strp=0;
414
415         return str;
416 }
417
418 static unsigned int
419 ntoh(unsigned char h)
420 {
421         if((h>='0')&&(h<='9')){
422                 return h-'0';
423         }
424
425         if((h>='A')&&(h<='F')){
426                 return h+10-'A';
427         }
428
429         if((h>='a')&&(h<='f')){
430                 return h+10-'a';
431         }
432
433         return 0;
434 }
435
436 /*
437  * Convert a hex string to an unsigned 64-bit integer.
438  */
439 unsigned char *
440 htou64(const char *u64str, unsigned char *u64int)
441 {
442         int i,len;
443         char str[16];
444         const char *strp;
445
446         if(!u64str){
447                 return NULL;
448         }
449
450         /* verify that the string is ok */
451         if( (u64str[0]!='0')
452         ||  (u64str[1]!='x') ){
453                 return NULL;
454         }
455
456         for(strp=u64str+2;*strp;strp++){
457                 if((*strp>='0')&&(*strp<='9')){
458                         continue;
459                 }
460                 if((*strp>='A')&&(*strp<='F')){
461                         continue;
462                 }
463                 if((*strp>='a')&&(*strp<='f')){
464                         continue;
465                 }
466                 return NULL;
467         }
468
469         /* clear the result vector */
470         for(i=0;i<8;i++){
471                 u64int[i]=0;
472         }
473
474         /* get len of input string */
475         for(len=0,strp=u64str+2;len<16;len++,strp++){
476                 if((*strp>='0')&&(*strp<='9')){
477                         continue;
478                 }
479                 if((*strp>='A')&&(*strp<='F')){
480                         continue;
481                 }
482                 if((*strp>='a')&&(*strp<='f')){
483                         continue;
484                 }
485                 break;
486         }
487         for(i=0;i<16;i++){
488                 str[i]='0';
489         }
490         for(i=0;i<len;i++){
491                 str[15-i]=u64str[len+1-i];
492         }
493
494
495         for(i=0;i<8;i++){
496                 u64int[i]=(ntoh(str[i*2])<<4)
497                         | ntoh(str[1+i*2]);
498         }
499
500         return u64int;
501 }
502
503 #ifdef TEST_DEBUG
504 #include <stdio.h>
505
506 int main(void)
507 {
508         char i998877665544331[8] =
509             {0x0, 0x23, 0x7c, 0xbd, 0x4c, 0x49, 0xd5, 0x6f};
510         char iminus9988776655443311[8] =
511             {0xff, 0xdc, 0x83, 0x42, 0xb3, 0xb6, 0x2a, 0x91};
512         char i9223372036854775807[8] =
513             {0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff};
514         char iminus1[8] =
515             {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff};
516         char iminus9223372036854775808[8] =
517             {0x80, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0};
518         char u9223372036854775808[8] =
519             {0x80, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0};
520         char u18446744073709551615[8] =
521             {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff};
522         char u0xaabbccdd00112233[8] =
523             {0xaa, 0xbb, 0xcc, 0xdd, 0x0, 0x11, 0x22, 0x33};
524         char t[8];
525
526         printf("%s (9988776655443311)\n",i64toa(i998877665544331));
527         printf("%s (-9988776655443311)\n",i64toa(iminus9988776655443311));
528         printf("%s (9223372036854775807)\n",i64toa(i9223372036854775807));
529         printf("%s (-1)\n",i64toa(iminus1));
530         printf("%s (-9223372036854775808)\n",i64toa(iminus9223372036854775808));
531
532         printf("%s (9988776655443311)\n",u64toa(i998877665544331));
533         printf("%s (9223372036854775807)\n",u64toa(i9223372036854775807));
534         printf("%s (9223372036854775808)\n",u64toa(u9223372036854775808));
535         printf("%s (18446744073709551615)\n",u64toa(u18446744073709551615));
536
537         printf("%s (0xaabbccdd00112233)\n",u64toh(u0xaabbccdd00112233));
538
539         printf("%s (55443311)\n",i64toa(atoi64("55443311",t)));
540         printf("%s (-55443311)\n",i64toa(atoi64("-55443311",t)));
541         printf("%s (9988776655443311)\n",i64toa(atoi64("9988776655443311",t)));
542         printf("%s (-9988776655443311)\n",i64toa(atoi64("-9988776655443311",t)));
543         printf("%s (9223372036854775807)\n",i64toa(atoi64("9223372036854775807",t)));
544         printf("%s (-1)\n",i64toa(atoi64("-1",t)));
545         printf("%s (-9223372036854775808)\n",i64toa(atoi64("-9223372036854775808",t)));
546
547         printf("%s (55443311)\n",u64toa(atou64("55443311",t)));
548         printf("%s (0x55443311)\n",u64toh(htou64("0x55443311",t)));
549         return 0;
550 }
551 #endif