git.rot13.org Git - simavr/blob - examples/board_reprap/src/c3/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_new_i(const char *s, void * (*_alloc)(size_t))
  83 {
  84         int l = s ? strlen(s) : 0;
  85         str_p r = (str_p)_alloc(sizeof(*r) + l + 1);
  86         r->hash = 0; r->len = l;
  87         if (s)
  88                 strcpy(r->str, s);
  89         return r;
  90 }
  91 static inline void str_free(str_p s)
  92 {
  93         if (s && !s->rom)
  94                 free(s);
  95 }
  96 static inline str_p str_new(const char *s)
  97 {
  98         return str_new_i(s, malloc);
  99 }
 100 static inline str_p str_anew(const char *s)
 101 {
 102         str_p r = str_new_i(s, alloca);
 103         r->rom = 1;
 104         return r;
 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_adup(const str_p s)
 115 {
 116         size_t l = sizeof(*s) + s->len + 1;
 117         str_p r = (str_p)alloca(l);
 118         memcpy(r, s, l);
 119         r->rom = 1;
 120         return r;
 121 }
 122 #endif
 123 static inline uint16_t str_hash(str_p s)
 124 {
 125         if (!s->hash) s->hash = crc16_string(s->str);
 126         return s->hash;
 127 }
 128 static inline int str_cmp(str_p s1, str_p s2)
 129 {
 130         if (s1 == s2) return 1;
 131         if (s1->len != s2->len) return 1;
 132         str_hash(s1);
 133         str_hash(s2);
 134         return s1->hash == s2->hash ? strcmp(s1->str, s2->str) : 1;
 135 }
 136
 137 /********************************************************************
 138  * Hash table of strings. Key/value pair
 139  ********************************************************************/
 140
 141 typedef struct str_hashval_t {
 142         str_p key;
 143         void * val;
 144 } str_hashval_t;
 145
 146 DECLARE_C_ARRAY(str_hashval_t, hashval_array, 16);
 147 IMPLEMENT_C_ARRAY(hashval_array);
 148
 149 #ifndef STR_HASH_SIZE
 150 #define STR_HASH_SIZE   512     // use 9 bits of the 16 of the CRC
 151 #endif
 152 /* uses bins to store the strings as per their hash values */
 153 typedef struct str_hash_t {
 154         hashval_array_t bin[STR_HASH_SIZE];
 155 } str_hash_t, *str_hash_p;
 156
 157 void
 158 str_hash_init(
 159                 str_hash_p h);
 160 void
 161 str_hash_add(
 162         str_hash_p h,
 163         str_p k,
 164         void * v);
 165
 166 void *
 167 str_hash_lookup(
 168         str_hash_p h,
 169         str_p k );
 170
 171 #endif /* __C_UTILS_H__ */