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 #include "c_array.h"
  30
  31 /********************************************************************
  32  * CRC16
  33  ********************************************************************/
  34
  35 static uint8_t _crc16_lh[16] = { 0x00, 0x10, 0x20, 0x30, 0x40, 0x50, 0x60,
  36         0x70, 0x81, 0x91, 0xA1, 0xB1, 0xC1, 0xD1, 0xE1, 0xF1 };
  37 static uint8_t _crc16_ll[16] = { 0x00, 0x21, 0x42, 0x63, 0x84, 0xA5, 0xC6,
  38         0xE7, 0x08, 0x29, 0x4A, 0x6B, 0x8C, 0xAD, 0xCE, 0xEF };
  39
  40 static uint16_t crc16_u4(uint16_t crc, uint8_t val)
  41 {
  42         uint8_t h = crc >> 8, l = crc & 0xff;
  43         uint8_t t = (h >> 4) ^ val;
  44
  45         // Shift the CRC Register left 4 bits
  46         h = (h << 4) | (l >> 4);
  47         l = l << 4;
  48         // Do the table lookups and XOR the result into the CRC Tables
  49         h = h ^ _crc16_lh[t];
  50         l = l ^ _crc16_ll[t];
  51         return (h << 8) | l;
  52 }
  53
  54 static uint16_t crc16_update(uint16_t crc, uint8_t val)
  55 {
  56         crc = crc16_u4(crc, val >> 4); // High nibble first
  57         crc = crc16_u4(crc, val & 0x0F); // Low nibble
  58         return crc;
  59 }
  60
  61 static uint16_t crc16_string(char * str)
  62 {
  63         uint16_t crc = 0xffff;
  64         while (*str)
  65                 crc = crc16_update(crc, *str++);
  66         return crc;
  67 }
  68
  69 /********************************************************************
  70  * Hashed strings
  71  ********************************************************************/
  72
  73 #include <string.h>
  74 typedef struct str_t {
  75         uint32_t hash : 16, rom : 1,  len : 15;
  76         char str[0];
  77 } str_t, *str_p;
  78
  79 static inline str_p str_new_i(const char *s, void * (*_alloc)(size_t))
  80 {
  81         int l = s ? strlen(s) : 0;
  82         str_p r = (str_p)_alloc(sizeof(*r) + l + 1);
  83         r->hash = 0; r->len = l;
  84         if (s)
  85                 strcpy(r->str, s);
  86         return r;
  87 }
  88 static inline void str_free(str_p s)
  89 {
  90         if (s && !s->rom)
  91                 free(s);
  92 }
  93 static inline str_p str_new(const char *s)
  94 {
  95         return str_new_i(s, malloc);
  96 }
  97 static inline str_p str_anew(const char *s)
  98 {
  99         str_p r = str_new_i(s, alloca);
 100         r->rom = 1;
 101         return r;
 102 }
 103 static inline str_p str_dup(const str_p s)
 104 {
 105         size_t l = sizeof(*s) + s->len + 1;
 106         str_p r = (str_p)malloc(l);
 107         memcpy(r, s, l);
 108         return r;
 109 }
 110 static inline str_p str_adup(const str_p s)
 111 {
 112         size_t l = sizeof(*s) + s->len + 1;
 113         str_p r = (str_p)alloca(l);
 114         memcpy(r, s, l);
 115         r->rom = 1;
 116         return r;
 117 }
 118 static inline uint16_t str_hash(str_p s)
 119 {
 120         if (!s->hash) s->hash = crc16_string(s->str);
 121         return s->hash;
 122 }
 123 static inline int str_cmp(str_p s1, str_p s2)
 124 {
 125         if (s1 == s2) return 1;
 126         if (s1->len != s2->len) return 1;
 127         str_hash(s1);
 128         str_hash(s2);
 129         return s1->hash == s2->hash ? strcmp(s1->str, s2->str) : 1;
 130 }
 131
 132 /********************************************************************
 133  * Hash table of strings. Key/value pair
 134  ********************************************************************/
 135
 136 typedef struct str_hashval_t {
 137         str_p key;
 138         void * val;
 139 } str_hashval_t;
 140
 141 DECLARE_C_ARRAY(str_hashval_t, hashval_array, 16);
 142 IMPLEMENT_C_ARRAY(hashval_array);
 143
 144 #ifndef STR_HASH_SIZE
 145 #define STR_HASH_SIZE   512     // use 9 bits of the 16 of the CRC
 146 #endif
 147 /* uses bins to store the strings as per their hash values */
 148 typedef struct str_hash_t {
 149         hashval_array_t bin[STR_HASH_SIZE];
 150 } str_hash_t, *str_hash_p;
 151
 152 void
 153 str_hash_init(
 154                 str_hash_p h);
 155 void
 156 str_hash_add(
 157         str_hash_p h,
 158         str_p k,
 159         void * v);
 160
 161 void *
 162 str_hash_lookup(
 163         str_hash_p h,
 164         str_p k );
 165
 166 #endif /* __C_UTILS_H__ */