git.rot13.org Git - simavr/blob - examples/shared/libc3/src/c_utils.h

   1 /*
   2         c_utils.h
   3
   4         Copyright 2008-11 Michel Pollet <buserror@gmail.com>
   5
   6         This program cross examines a root filesystem, loads all the elf
   7         files it can find, see what other library they load and then
   8         find the orphans. In then remove the orphans as "user" for it's
   9         dependencies and continues removing until everything has at least
  10         one user, OR is a program itself (ie, not a shared library)
  11
  12         cross_linker is free software: you can redistribute it and/or modify
  13         it under the terms of the GNU General Public License as published by
  14         the Free Software Foundation, either version 3 of the License, or
  15         (at your option) any later version.
  16
  17         cross_linker is distributed in the hope that it will be useful,
  18         but WITHOUT ANY WARRANTY; without even the implied warranty of
  19         MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20         GNU General Public License for more details.
  21
  22         You should have received a copy of the GNU General Public License
  23         along with cross_linker.  If not, see <http://www.gnu.org/licenses/>.
  24  */
  25
  26 #ifndef __C_UTILS_H__
  27 #define __C_UTILS_H__
  28
  29 #ifndef NO_ALLOCA
  30 #include <alloca.h>
  31 #endif
  32 #include "c_array.h"
  33
  34 /********************************************************************
  35  * CRC16
  36  ********************************************************************/
  37
  38 static uint8_t _crc16_lh[16] = { 0x00, 0x10, 0x20, 0x30, 0x40, 0x50, 0x60,
  39         0x70, 0x81, 0x91, 0xA1, 0xB1, 0xC1, 0xD1, 0xE1, 0xF1 };
  40 static uint8_t _crc16_ll[16] = { 0x00, 0x21, 0x42, 0x63, 0x84, 0xA5, 0xC6,
  41         0xE7, 0x08, 0x29, 0x4A, 0x6B, 0x8C, 0xAD, 0xCE, 0xEF };
  42
  43 static uint16_t crc16_u4(uint16_t crc, uint8_t val)
  44 {
  45         uint8_t h = crc >> 8, l = crc & 0xff;
  46         uint8_t t = (h >> 4) ^ val;
  47
  48         // Shift the CRC Register left 4 bits
  49         h = (h << 4) | (l >> 4);
  50         l = l << 4;
  51         // Do the table lookups and XOR the result into the CRC Tables
  52         h = h ^ _crc16_lh[t];
  53         l = l ^ _crc16_ll[t];
  54         return (h << 8) | l;
  55 }
  56
  57 static uint16_t crc16_update(uint16_t crc, uint8_t val)
  58 {
  59         crc = crc16_u4(crc, val >> 4); // High nibble first
  60         crc = crc16_u4(crc, val & 0x0F); // Low nibble
  61         return crc;
  62 }
  63
  64 static uint16_t crc16_string(char * str)
  65 {
  66         uint16_t crc = 0xffff;
  67         while (*str)
  68                 crc = crc16_update(crc, *str++);
  69         return crc;
  70 }
  71
  72 /********************************************************************
  73  * Hashed strings
  74  ********************************************************************/
  75
  76 #include <string.h>
  77 typedef struct str_t {
  78         uint32_t hash : 16, rom : 1,  len : 15;
  79         char str[0];
  80 } str_t, *str_p;
  81
  82 static inline str_p str_alloc(size_t len)
  83 {
  84         str_p r = (str_p)malloc(sizeof(*r) + len + 1);
  85         r->rom = r->hash = 0; r->len = len;
  86         return r;
  87 }
  88 static inline str_p str_new_i(const char *s, void * (*_alloc)(size_t))
  89 {
  90         int l = s ? strlen(s) : 0;
  91         str_p r = (str_p)_alloc(sizeof(*r) + l + 1);
  92         r->hash = 0; r->len = l;
  93         if (s)
  94                 strcpy(r->str, s);
  95         return r;
  96 }
  97 static inline void str_free(str_p s)
  98 {
  99         if (s && !s->rom)
 100                 free(s);
 101 }
 102 static inline str_p str_new(const char *s)
 103 {
 104         return str_new_i(s, malloc);
 105 }
 106 static inline str_p str_dup(const str_p s)
 107 {
 108         size_t l = sizeof(*s) + s->len + 1;
 109         str_p r = (str_p)malloc(l);
 110         memcpy(r, s, l);
 111         return r;
 112 }
 113 #ifndef NO_ALLOCA
 114 static inline str_p str_anew(const char *s)
 115 {
 116         str_p r = str_new_i(s, alloca);
 117         r->rom = 1;
 118         return r;
 119 }
 120 static inline str_p str_adup(const str_p s)
 121 {
 122         size_t l = sizeof(*s) + s->len + 1;
 123         str_p r = (str_p)alloca(l);
 124         memcpy(r, s, l);
 125         r->rom = 1;
 126         return r;
 127 }
 128 #endif
 129 static inline uint16_t str_hash(str_p s)
 130 {
 131         if (!s->hash) s->hash = crc16_string(s->str);
 132         return s->hash;
 133 }
 134 static inline int str_cmp(str_p s1, str_p s2)
 135 {
 136         if (s1 == s2) return 1;
 137         if (s1->len != s2->len) return 1;
 138         str_hash(s1);
 139         str_hash(s2);
 140         return s1->hash == s2->hash ? strcmp(s1->str, s2->str) : 1;
 141 }
 142
 143 /********************************************************************
 144  * Hash table of strings. Key/value pair
 145  ********************************************************************/
 146
 147 typedef struct str_hashval_t {
 148         str_p key;
 149         void * val;
 150 } str_hashval_t;
 151
 152 DECLARE_C_ARRAY(str_hashval_t, hashval_array, 16);
 153 IMPLEMENT_C_ARRAY(hashval_array);
 154
 155 #ifndef STR_HASH_SIZE
 156 #define STR_HASH_SIZE   512     // use 9 bits of the 16 of the CRC
 157 #endif
 158 /* uses bins to store the strings as per their hash values */
 159 typedef struct str_hash_t {
 160         hashval_array_t bin[STR_HASH_SIZE];
 161 } str_hash_t, *str_hash_p;
 162
 163 void
 164 str_hash_init(
 165                 str_hash_p h);
 166 void
 167 str_hash_add(
 168         str_hash_p h,
 169         str_p k,
 170         void * v);
 171
 172 void *
 173 str_hash_lookup(
 174         str_hash_p h,
 175         str_p k );
 176
 177 #endif /* __C_UTILS_H__ */