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