string.c

   1 // Copyright (2013) Jann Horn <jann@thejh.net>
   2 // This code is licensed under the AGPLv3.
   3
   4 #include <string.h>
   5 #include <emmintrin.h>
   6 HEADER #include <stdint.h>
   7
   8 HEADER #define streq(a,b) (!strcmp((a),(b)))
   9
  10 HEADER #define TPRINTF(name, ...)                                               \
  11 HEADER   char *name;                                                            \
  12 HEADER   do {                                                                   \
  13 HEADER     int __tprintf_size = snprintf(NULL, 0, __VA_ARGS__);                 \
  14 HEADER     assert(__tprintf_size != -1);                                        \
  15 HEADER     name = alloca(__tprintf_size+1);                                     \
  16 HEADER     int __tprintf_size2 = snprintf(name, __tprintf_size+1, __VA_ARGS__); \
  17 HEADER     assert(__tprintf_size == __tprintf_size2);                           \
  18 HEADER   } while (0); //////////////////////////////////////////////////////////
  19
  20 PUBLIC_FN int count_char_occurences(char *s, char c) {
  21   int n=0;
  22   while (*s) {
  23     if (*s==c) n++;
  24     s++;
  25   }
  26   return n;
  27 }
  28
  29 // For big buffers.
  30 PUBLIC_FN size_t count_char_occurences_in_buf(char *b, size_t bl, char c) {
  31   char *be = b+bl;
  32   size_t res = 0;
  33
  34   #ifdef __SSE2__
  35   #include <emmintrin.h>
  36
  37   // do it the simple way until we get to the next 16-byte-aligned address
  38   while ((((uint64_t)b)&0xf) && b<be) if (*(b++)==c) res++;
  39
  40   // the aligned end is the last 8-byte-aligned byte IN this buffer
  41   char *bea = (char *) (((uint64_t)be-1)&~0xf);
  42   // prepare a 128-bit value that contains 16 times `c`
  43   __m128i cx;
  44   memset(&cx, c, 16);
  45   // we have an 16-byte-aligned buffer ready – let's do it!
  46   __m128i *bi = (__m128i *)b;
  47   while (((char*)bi)<bea) {
  48     // This intrinsic does a byte-wise compare, storing the results byte-wise,
  49     // too. 0xff means equal, 0x00 means not equal.
  50     __m128i r = _mm_cmpeq_epi8(cx, *bi);
  51     int64_t *r_64 = (int64_t*)&r;
  52     if ((r_64[0]|r_64[1])) {
  53       char *r_8 = (char *)&r;
  54       // we have at least one hit in those 16 chars. narrow it down to eight,
  55       // then check those eight
  56       if (r_64[0]) {
  57         if (r_8[ 0]) res++;   if (r_8[ 1]) res++;
  58         if (r_8[ 2]) res++;   if (r_8[ 3]) res++;
  59         if (r_8[ 4]) res++;   if (r_8[ 5]) res++;
  60         if (r_8[ 6]) res++;   if (r_8[ 7]) res++;
  61       }
  62       if (r_64[1]) {
  63         if (r_8[ 8]) res++;   if (r_8[ 9]) res++;
  64         if (r_8[10]) res++;   if (r_8[11]) res++;
  65         if (r_8[12]) res++;   if (r_8[13]) res++;
  66         if (r_8[14]) res++;   if (r_8[15]) res++;
  67       }
  68     }
  69     bi++;
  70   }
  71
  72   // do the last few bytes the slow way, too
  73   b = (char *)bi;
  74   #endif
  75
  76   // this is also the fallback in case the CPU can't do this
  77   while (b<be) if (*(b++)==c) res++;
  78
  79   return res;
  80 }
  81
  82 // For big buffers.
  83 PUBLIC_FN int count_and_replace_char_occurences_in_buf(char *b, size_t bl, char c, char new_c) {
  84   char *be = b+bl;
  85   int res = 0;
  86
  87   #ifdef __SSE2__
  88   #include <emmintrin.h>
  89
  90   // do it the simple way until we get to the next 16-byte-aligned address
  91   while ((((uint64_t)b)&0xf) && b<be) if (*(b++)==c) res++;
  92
  93   // the aligned end is the last 8-byte-aligned byte IN this buffer
  94   char *bea = (char *) (((uint64_t)be-1)&~0xf);
  95   // prepare a 128-bit value that contains 16 times `c`
  96   __m128i cx;
  97   memset(&cx, c, 16);
  98   // we have an 16-byte-aligned buffer ready – let's do it!
  99   __m128i *bi = (__m128i *)b;
 100   while (((char*)bi)<bea) {
 101     // This intrinsic does a byte-wise compare, storing the results byte-wise,
 102     // too. 0xff means equal, 0x00 means not equal.
 103     __m128i r = _mm_cmpeq_epi8(cx, *bi);
 104     int64_t *r_64 = (int64_t*)&r;
 105     if ((r_64[0]|r_64[1])) {
 106       char *r_8 = (char *)&r;
 107       // we have at least one hit in those 16 chars. narrow it down to eight,
 108       // then check those eight
 109       if (r_64[0]) {
 110         if (r_8[ 0]) r_8[ 0]=new_c, res++;   if (r_8[ 1]) r_8[ 1]=new_c, res++;
 111         if (r_8[ 2]) r_8[ 2]=new_c, res++;   if (r_8[ 3]) r_8[ 3]=new_c, res++;
 112         if (r_8[ 0]) r_8[ 4]=new_c, res++;   if (r_8[ 1]) r_8[ 5]=new_c, res++;
 113         if (r_8[ 2]) r_8[ 6]=new_c, res++;   if (r_8[ 3]) r_8[ 7]=new_c, res++;
 114       }
 115       if (r_64[1]) {
 116         if (r_8[ 8]) r_8[ 8]=new_c, res++;   if (r_8[ 9]) r_8[ 9]=new_c, res++;
 117         if (r_8[10]) r_8[10]=new_c, res++;   if (r_8[11]) r_8[11]=new_c, res++;
 118         if (r_8[12]) r_8[12]=new_c, res++;   if (r_8[13]) r_8[13]=new_c, res++;
 119         if (r_8[14]) r_8[14]=new_c, res++;   if (r_8[15]) r_8[15]=new_c, res++;
 120       }
 121     }
 122     bi++;
 123   }
 124
 125   // do the last few bytes the slow way, too
 126   b = (char *)bi;
 127   #endif
 128
 129   // this is also the fallback in case the CPU can't do this
 130   while (b<be) if (*(b++)==c) res++;
 131
 132   return res;
 133 }
 134
 135 // memcpy plus terminating nullbyte
 136 PUBLIC_FN void *memcpyn(void *d, const void *s, size_t n) {
 137   memcpy(d, s, n);
 138   char *d_ = d;
 139   d_[n] = '\0';
 140   return d;
 141 }
 142
 143 // Wipe out whitespace characters at the end of str using nullbytes.
 144 PUBLIC_FN void trim_end(char *str, char *whitespace) {
 145   for (char *p = str+strlen(str)-1; p>=str; p--) {
 146     if (!strchr(whitespace, *p)) break;
 147     *p = '\0';
 148     p--;
 149   }
 150 }
 151
 152 PUBLIC_FN int ends_with(char *str, char *sub) {
 153   size_t str_len = strlen(str);
 154   size_t sub_len = strlen(sub);
 155   if (sub_len>str_len) return 0;
 156   return streq(str+str_len-sub_len, sub);
 157 }
 158
 159 PUBLIC_FN char **buf_to_linearray(char *buf, ssize_t buflen) {
 160   if (buflen == -1) buflen = strlen(buf);
 161   size_t linecount = count_char_occurences_in_buf(buf, buflen, '\n')+1;
 162   char **ret = malloc(linecount * sizeof(char*) + 1);
 163   ret[linecount] = NULL;
 164   if (ret == NULL) return NULL;
 165   char **r = ret;
 166   *(r++) = buf; /* first line starts at byte zero */
 167   char *b = buf;
 168   char *be = buf+buflen;
 169   while (b<be) {
 170     if (*b == '\n') {
 171       *b = '\0';
 172       *(r++) = b+1;
 173     }
 174     b++;
 175   }
 176   return ret;
 177 }