src/buffer.c

   1 #include "first.h"
   2
   3 #include "buffer.h"
   4
   5 #include <stdlib.h>
   6 #include <string.h>
   7
   8 #include <stdio.h>
   9 #include <assert.h>
  10 #include <ctype.h>
  11
  12 static const char hex_chars[] = "0123456789abcdef";
  13
  14 /**
  15  * init the buffer
  16  *
  17  */
  18
  19 buffer* buffer_init(void) {
  20         buffer *b;
  21
  22         b = malloc(sizeof(*b));
  23         force_assert(b);
  24
  25         b->ptr = NULL;
  26         b->size = 0;
  27         b->used = 0;
  28
  29         return b;
  30 }
  31
  32 buffer *buffer_init_buffer(const buffer *src) {
  33         buffer *b = buffer_init();
  34         buffer_copy_buffer(b, src);
  35         return b;
  36 }
  37
  38 buffer *buffer_init_string(const char *str) {
  39         buffer *b = buffer_init();
  40         buffer_copy_string(b, str);
  41         return b;
  42 }
  43
  44 void buffer_free(buffer *b) {
  45         if (NULL == b) return;
  46
  47         free(b->ptr);
  48         free(b);
  49 }
  50
  51 void buffer_reset(buffer *b) {
  52         if (NULL == b) return;
  53
  54         /* limit don't reuse buffer larger than ... bytes */
  55         if (b->size > BUFFER_MAX_REUSE_SIZE) {
  56                 free(b->ptr);
  57                 b->ptr = NULL;
  58                 b->size = 0;
  59         } else if (b->size > 0) {
  60                 b->ptr[0] = '\0';
  61         }
  62
  63         b->used = 0;
  64 }
  65
  66 void buffer_move(buffer *b, buffer *src) {
  67         buffer tmp;
  68
  69         if (NULL == b) {
  70                 buffer_reset(src);
  71                 return;
  72         }
  73         buffer_reset(b);
  74         if (NULL == src) return;
  75
  76         tmp = *src; *src = *b; *b = tmp;
  77 }
  78
  79 #define BUFFER_PIECE_SIZE 64
  80 static size_t buffer_align_size(size_t size) {
  81         size_t align = BUFFER_PIECE_SIZE - (size % BUFFER_PIECE_SIZE);
  82         /* overflow on unsinged size_t is defined to wrap around */
  83         if (size + align < size) return size;
  84         return size + align;
  85 }
  86
  87 /* make sure buffer is at least "size" big. discard old data */
  88 static void buffer_alloc(buffer *b, size_t size) {
  89         force_assert(NULL != b);
  90         if (0 == size) size = 1;
  91
  92         if (size <= b->size) return;
  93
  94         if (NULL != b->ptr) free(b->ptr);
  95
  96         b->used = 0;
  97         b->size = buffer_align_size(size);
  98         b->ptr = malloc(b->size);
  99
 100         force_assert(NULL != b->ptr);
 101 }
 102
 103 /* make sure buffer is at least "size" big. keep old data */
 104 static void buffer_realloc(buffer *b, size_t size) {
 105         force_assert(NULL != b);
 106         if (0 == size) size = 1;
 107
 108         if (size <= b->size) return;
 109
 110         b->size = buffer_align_size(size);
 111         b->ptr = realloc(b->ptr, b->size);
 112
 113         force_assert(NULL != b->ptr);
 114 }
 115
 116
 117 char* buffer_string_prepare_copy(buffer *b, size_t size) {
 118         force_assert(NULL != b);
 119         force_assert(size + 1 > size);
 120
 121         buffer_alloc(b, size + 1);
 122
 123         b->used = 1;
 124         b->ptr[0] = '\0';
 125
 126         return b->ptr;
 127 }
 128
 129 char* buffer_string_prepare_append(buffer *b, size_t size) {
 130         force_assert(NULL !=  b);
 131
 132         if (buffer_string_is_empty(b)) {
 133                 return buffer_string_prepare_copy(b, size);
 134         } else {
 135                 size_t req_size = b->used + size;
 136
 137                 /* not empty, b->used already includes a terminating 0 */
 138                 force_assert(req_size >= b->used);
 139
 140                 /* check for overflow: unsigned overflow is defined to wrap around */
 141                 force_assert(req_size >= b->used);
 142
 143                 buffer_realloc(b, req_size);
 144
 145                 return b->ptr + b->used - 1;
 146         }
 147 }
 148
 149 void buffer_string_set_length(buffer *b, size_t len) {
 150         force_assert(NULL != b);
 151         force_assert(len + 1 > len);
 152
 153         buffer_realloc(b, len + 1);
 154
 155         b->used = len + 1;
 156         b->ptr[len] = '\0';
 157 }
 158
 159 void buffer_commit(buffer *b, size_t size)
 160 {
 161         force_assert(NULL != b);
 162         force_assert(b->size > 0);
 163
 164         if (0 == b->used) b->used = 1;
 165
 166         if (size > 0) {
 167                 /* check for overflow: unsigned overflow is defined to wrap around */
 168                 force_assert(b->used + size > b->used);
 169
 170                 force_assert(b->used + size <= b->size);
 171                 b->used += size;
 172         }
 173
 174         b->ptr[b->used - 1] = '\0';
 175 }
 176
 177 void buffer_copy_string(buffer *b, const char *s) {
 178         buffer_copy_string_len(b, s, NULL != s ? strlen(s) : 0);
 179 }
 180
 181 void buffer_copy_string_len(buffer *b, const char *s, size_t s_len) {
 182         force_assert(NULL != b);
 183         force_assert(NULL != s || s_len == 0);
 184
 185         buffer_string_prepare_copy(b, s_len);
 186
 187         if (0 != s_len) memcpy(b->ptr, s, s_len);
 188
 189         buffer_commit(b, s_len);
 190 }
 191
 192 void buffer_copy_buffer(buffer *b, const buffer *src) {
 193         if (NULL == src || 0 == src->used) {
 194                 buffer_string_prepare_copy(b, 0);
 195                 b->used = 0; /* keep special empty state for now */
 196         } else {
 197                 buffer_copy_string_len(b, src->ptr, buffer_string_length(src));
 198         }
 199 }
 200
 201 void buffer_append_string(buffer *b, const char *s) {
 202         buffer_append_string_len(b, s, NULL != s ? strlen(s) : 0);
 203 }
 204
 205 /**
 206  * append a string to the end of the buffer
 207  *
 208  * the resulting buffer is terminated with a '\0'
 209  * s is treated as a un-terminated string (a \0 is handled a normal character)
 210  *
 211  * @param b a buffer
 212  * @param s the string
 213  * @param s_len size of the string (without the terminating \0)
 214  */
 215
 216 void buffer_append_string_len(buffer *b, const char *s, size_t s_len) {
 217         char *target_buf;
 218
 219         force_assert(NULL != b);
 220         force_assert(NULL != s || s_len == 0);
 221
 222         target_buf = buffer_string_prepare_append(b, s_len);
 223
 224         if (0 == s_len) return; /* nothing to append */
 225
 226         memcpy(target_buf, s, s_len);
 227
 228         buffer_commit(b, s_len);
 229 }
 230
 231 void buffer_append_string_buffer(buffer *b, const buffer *src) {
 232         if (NULL == src) {
 233                 buffer_append_string_len(b, NULL, 0);
 234         } else {
 235                 buffer_append_string_len(b, src->ptr, buffer_string_length(src));
 236         }
 237 }
 238
 239 void buffer_append_uint_hex(buffer *b, uintmax_t value) {
 240         char *buf;
 241         int shift = 0;
 242
 243         {
 244                 uintmax_t copy = value;
 245                 do {
 246                         copy >>= 8;
 247                         shift += 2; /* counting nibbles (4 bits) */
 248                 } while (0 != copy);
 249         }
 250
 251         buf = buffer_string_prepare_append(b, shift);
 252         buffer_commit(b, shift); /* will fill below */
 253
 254         shift <<= 2; /* count bits now */
 255         while (shift > 0) {
 256                 shift -= 4;
 257                 *(buf++) = hex_chars[(value >> shift) & 0x0F];
 258         }
 259 }
 260
 261 static char* utostr(char * const buf_end, uintmax_t val) {
 262         char *cur = buf_end;
 263         do {
 264                 int mod = val % 10;
 265                 val /= 10;
 266                 /* prepend digit mod */
 267                 *(--cur) = (char) ('0' + mod);
 268         } while (0 != val);
 269         return cur;
 270 }
 271
 272 static char* itostr(char * const buf_end, intmax_t val) {
 273         char *cur = buf_end;
 274         if (val >= 0) return utostr(buf_end, (uintmax_t) val);
 275
 276         /* can't take absolute value, as it isn't defined for INTMAX_MIN */
 277         do {
 278                 int mod = val % 10;
 279                 val /= 10;
 280                 /* val * 10 + mod == orig val, -10 < mod < 10 */
 281                 /* we want a negative mod */
 282                 if (mod > 0) {
 283                         mod -= 10;
 284                         val += 1;
 285                 }
 286                 /* prepend digit abs(mod) */
 287                 *(--cur) = (char) ('0' + (-mod));
 288         } while (0 != val);
 289         *(--cur) = '-';
 290
 291         return cur;
 292 }
 293
 294 void buffer_append_int(buffer *b, intmax_t val) {
 295         char buf[LI_ITOSTRING_LENGTH];
 296         char* const buf_end = buf + sizeof(buf);
 297         char *str;
 298
 299         force_assert(NULL != b);
 300
 301         str = itostr(buf_end, val);
 302         force_assert(buf_end > str && str >= buf);
 303
 304         buffer_append_string_len(b, str, buf_end - str);
 305 }
 306
 307 void buffer_copy_int(buffer *b, intmax_t val) {
 308         force_assert(NULL != b);
 309
 310         b->used = 0;
 311         buffer_append_int(b, val);
 312 }
 313
 314 void buffer_append_strftime(buffer *b, const char *format, const struct tm *tm) {
 315         size_t r;
 316         char* buf;
 317         force_assert(NULL != b);
 318         force_assert(NULL != tm);
 319
 320         if (NULL == format || '\0' == format[0]) {
 321                 /* empty format */
 322                 buffer_string_prepare_append(b, 0);
 323                 return;
 324         }
 325
 326         buf = buffer_string_prepare_append(b, 255);
 327         r = strftime(buf, buffer_string_space(b), format, tm);
 328
 329         /* 0 (in some apis buffer_string_space(b)) signals the string may have
 330          * been too small; but the format could also just have lead to an empty
 331          * string
 332          */
 333         if (0 == r || r >= buffer_string_space(b)) {
 334                 /* give it a second try with a larger string */
 335                 buf = buffer_string_prepare_append(b, 4095);
 336                 r = strftime(buf, buffer_string_space(b), format, tm);
 337         }
 338
 339         if (r >= buffer_string_space(b)) r = 0;
 340
 341         buffer_commit(b, r);
 342 }
 343
 344
 345 void li_itostrn(char *buf, size_t buf_len, intmax_t val) {
 346         char p_buf[LI_ITOSTRING_LENGTH];
 347         char* const p_buf_end = p_buf + sizeof(p_buf);
 348         char* str = p_buf_end - 1;
 349         *str = '\0';
 350
 351         str = itostr(str, val);
 352         force_assert(p_buf_end > str && str >= p_buf);
 353
 354         force_assert(buf_len >= (size_t) (p_buf_end - str));
 355         memcpy(buf, str, p_buf_end - str);
 356 }
 357
 358 void li_utostrn(char *buf, size_t buf_len, uintmax_t val) {
 359         char p_buf[LI_ITOSTRING_LENGTH];
 360         char* const p_buf_end = p_buf + sizeof(p_buf);
 361         char* str = p_buf_end - 1;
 362         *str = '\0';
 363
 364         str = utostr(str, val);
 365         force_assert(p_buf_end > str && str >= p_buf);
 366
 367         force_assert(buf_len >= (size_t) (p_buf_end - str));
 368         memcpy(buf, str, p_buf_end - str);
 369 }
 370
 371 char int2hex(char c) {
 372         return hex_chars[(c & 0x0F)];
 373 }
 374
 375 /* converts hex char (0-9, A-Z, a-z) to decimal.
 376  * returns 0xFF on invalid input.
 377  */
 378 char hex2int(unsigned char hex) {
 379         unsigned char value = hex - '0';
 380         if (value > 9) {
 381                 hex |= 0x20; /* to lower case */
 382                 value = hex - 'a' + 10;
 383                 if (value < 10) value = 0xff;
 384         }
 385         if (value > 15) value = 0xff;
 386
 387         return value;
 388 }
 389
 390 char * buffer_search_string_len(buffer *b, const char *needle, size_t len) {
 391         size_t i;
 392         force_assert(NULL != b);
 393         force_assert(0 != len && NULL != needle); /* empty needles not allowed */
 394
 395         if (b->used < len) return NULL;
 396
 397         for(i = 0; i < b->used - len; i++) {
 398                 if (0 == memcmp(b->ptr + i, needle, len)) {
 399                         return b->ptr + i;
 400                 }
 401         }
 402
 403         return NULL;
 404 }
 405
 406 int buffer_is_empty(const buffer *b) {
 407         return NULL == b || 0 == b->used;
 408 }
 409
 410 int buffer_string_is_empty(const buffer *b) {
 411         return 0 == buffer_string_length(b);
 412 }
 413
 414 /**
 415  * check if two buffer contain the same data
 416  *
 417  * HISTORY: this function was pretty much optimized, but didn't handled
 418  * alignment properly.
 419  */
 420
 421 int buffer_is_equal(const buffer *a, const buffer *b) {
 422         force_assert(NULL != a && NULL != b);
 423
 424         if (a->used != b->used) return 0;
 425         if (a->used == 0) return 1;
 426
 427         return (0 == memcmp(a->ptr, b->ptr, a->used));
 428 }
 429
 430 int buffer_is_equal_string(const buffer *a, const char *s, size_t b_len) {
 431         force_assert(NULL != a && NULL != s);
 432         force_assert(b_len + 1 > b_len);
 433
 434         if (a->used != b_len + 1) return 0;
 435         if (0 != memcmp(a->ptr, s, b_len)) return 0;
 436         if ('\0' != a->ptr[a->used-1]) return 0;
 437
 438         return 1;
 439 }
 440
 441 /* buffer_is_equal_caseless_string(b, CONST_STR_LEN("value")) */
 442 int buffer_is_equal_caseless_string(const buffer *a, const char *s, size_t b_len) {
 443         force_assert(NULL != a);
 444         if (a->used != b_len + 1) return 0;
 445         force_assert('\0' == a->ptr[a->used - 1]);
 446
 447         return (0 == strcasecmp(a->ptr, s));
 448 }
 449
 450 int buffer_caseless_compare(const char *a, size_t a_len, const char *b, size_t b_len) {
 451         size_t const len = (a_len < b_len) ? a_len : b_len;
 452         size_t i;
 453
 454         for (i = 0; i < len; ++i) {
 455                 unsigned char ca = a[i], cb = b[i];
 456                 if (ca == cb) continue;
 457
 458                 /* always lowercase for transitive results */
 459                 if (ca >= 'A' && ca <= 'Z') ca |= 32;
 460                 if (cb >= 'A' && cb <= 'Z') cb |= 32;
 461
 462                 if (ca == cb) continue;
 463                 return ((int)ca) - ((int)cb);
 464         }
 465         if (a_len == b_len) return 0;
 466         return a_len < b_len ? -1 : 1;
 467 }
 468
 469 int buffer_is_equal_right_len(const buffer *b1, const buffer *b2, size_t len) {
 470         /* no len -> equal */
 471         if (len == 0) return 1;
 472
 473         /* len > 0, but empty buffers -> not equal */
 474         if (b1->used == 0 || b2->used == 0) return 0;
 475
 476         /* buffers too small -> not equal */
 477         if (b1->used - 1 < len || b2->used - 1 < len) return 0;
 478
 479         return 0 == memcmp(b1->ptr + b1->used - 1 - len, b2->ptr + b2->used - 1 - len, len);
 480 }
 481
 482 void li_tohex(char *buf, size_t buf_len, const char *s, size_t s_len) {
 483         size_t i;
 484         force_assert(2 * s_len > s_len);
 485         force_assert(2 * s_len < buf_len);
 486
 487         for (i = 0; i < s_len; i++) {
 488                 buf[2*i] = hex_chars[(s[i] >> 4) & 0x0F];
 489                 buf[2*i+1] = hex_chars[s[i] & 0x0F];
 490         }
 491         buf[2*s_len] = '\0';
 492 }
 493
 494 void buffer_copy_string_hex(buffer *b, const char *in, size_t in_len) {
 495         /* overflow protection */
 496         force_assert(in_len * 2 > in_len);
 497
 498         buffer_string_set_length(b, 2 * in_len);
 499         li_tohex(b->ptr, buffer_string_space(b)+1, in, in_len);
 500 }
 501
 502 /* everything except: ! ( ) * - . 0-9 A-Z _ a-z ~ */
 503 static const char encoded_chars_rel_uri_part[] = {
 504         /*
 505         0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
 506         */
 507         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  00 -  0F control chars */
 508         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  10 -  1F */
 509         1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1,  /*  20 -  2F space " # $ % & ' + , / */
 510         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1,  /*  30 -  3F : ; < = > ? */
 511         1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  40 -  4F @ */
 512         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0,  /*  50 -  5F [ \ ] ^ */
 513         1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  60 -  6F ` */
 514         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1,  /*  70 -  7F { | } ~ DEL */
 515         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  80 -  8F */
 516         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  90 -  9F */
 517         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  A0 -  AF */
 518         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  B0 -  BF */
 519         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  C0 -  CF */
 520         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  D0 -  DF */
 521         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  E0 -  EF */
 522         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  F0 -  FF */
 523 };
 524
 525 /* everything except: ! ( ) * - . / 0-9 A-Z _ a-z ~ */
 526 static const char encoded_chars_rel_uri[] = {
 527         /*
 528         0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
 529         */
 530         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  00 -  0F control chars */
 531         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  10 -  1F */
 532         1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0,  /*  20 -  2F space " # $ % & ' + , */
 533         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1,  /*  30 -  3F : ; < = > ? */
 534         1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  40 -  4F @ */
 535         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0,  /*  50 -  5F [ \ ] ^ */
 536         1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  60 -  6F ` */
 537         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1,  /*  70 -  7F { | } ~ DEL */
 538         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  80 -  8F */
 539         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  90 -  9F */
 540         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  A0 -  AF */
 541         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  B0 -  BF */
 542         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  C0 -  CF */
 543         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  D0 -  DF */
 544         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  E0 -  EF */
 545         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  F0 -  FF */
 546 };
 547
 548 static const char encoded_chars_html[] = {
 549         /*
 550         0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
 551         */
 552         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  00 -  0F control chars */
 553         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  10 -  1F */
 554         0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  20 -  2F & */
 555         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0,  /*  30 -  3F < > */
 556         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  40 -  4F */
 557         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  50 -  5F */
 558         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  60 -  6F */
 559         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,  /*  70 -  7F DEL */
 560         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  80 -  8F */
 561         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  90 -  9F */
 562         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  A0 -  AF */
 563         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  B0 -  BF */
 564         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  C0 -  CF */
 565         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  D0 -  DF */
 566         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  E0 -  EF */
 567         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  F0 -  FF */
 568 };
 569
 570 static const char encoded_chars_minimal_xml[] = {
 571         /*
 572         0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
 573         */
 574         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  00 -  0F control chars */
 575         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  10 -  1F */
 576         0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  20 -  2F & */
 577         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0,  /*  30 -  3F < > */
 578         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  40 -  4F */
 579         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  50 -  5F */
 580         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  60 -  6F */
 581         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,  /*  70 -  7F DEL */
 582         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  80 -  8F */
 583         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  90 -  9F */
 584         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  A0 -  AF */
 585         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  B0 -  BF */
 586         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  C0 -  CF */
 587         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  D0 -  DF */
 588         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  E0 -  EF */
 589         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  F0 -  FF */
 590 };
 591
 592 static const char encoded_chars_hex[] = {
 593         /*
 594         0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
 595         */
 596         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  00 -  0F control chars */
 597         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  10 -  1F */
 598         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  20 -  2F */
 599         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  30 -  3F */
 600         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  40 -  4F */
 601         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  50 -  5F */
 602         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  60 -  6F */
 603         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  70 -  7F */
 604         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  80 -  8F */
 605         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  90 -  9F */
 606         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  A0 -  AF */
 607         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  B0 -  BF */
 608         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  C0 -  CF */
 609         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  D0 -  DF */
 610         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  E0 -  EF */
 611         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /*  F0 -  FF */
 612 };
 613
 614 static const char encoded_chars_http_header[] = {
 615         /*
 616         0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
 617         */
 618         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,  /*  00 -  0F */
 619         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  10 -  1F */
 620         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  20 -  2F */
 621         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  30 -  3F */
 622         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  40 -  4F */
 623         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  50 -  5F */
 624         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  60 -  6F */
 625         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  70 -  7F */
 626         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  80 -  8F */
 627         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  90 -  9F */
 628         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  A0 -  AF */
 629         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  B0 -  BF */
 630         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  C0 -  CF */
 631         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  D0 -  DF */
 632         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  E0 -  EF */
 633         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  /*  F0 -  FF */
 634 };
 635
 636
 637
 638 void buffer_append_string_encoded(buffer *b, const char *s, size_t s_len, buffer_encoding_t encoding) {
 639         unsigned char *ds, *d;
 640         size_t d_len, ndx;
 641         const char *map = NULL;
 642
 643         force_assert(NULL != b);
 644         force_assert(NULL != s || 0 == s_len);
 645
 646         if (0 == s_len) return;
 647
 648         switch(encoding) {
 649         case ENCODING_REL_URI:
 650                 map = encoded_chars_rel_uri;
 651                 break;
 652         case ENCODING_REL_URI_PART:
 653                 map = encoded_chars_rel_uri_part;
 654                 break;
 655         case ENCODING_HTML:
 656                 map = encoded_chars_html;
 657                 break;
 658         case ENCODING_MINIMAL_XML:
 659                 map = encoded_chars_minimal_xml;
 660                 break;
 661         case ENCODING_HEX:
 662                 map = encoded_chars_hex;
 663                 break;
 664         case ENCODING_HTTP_HEADER:
 665                 map = encoded_chars_http_header;
 666                 break;
 667         }
 668
 669         force_assert(NULL != map);
 670
 671         /* count to-be-encoded-characters */
 672         for (ds = (unsigned char *)s, d_len = 0, ndx = 0; ndx < s_len; ds++, ndx++) {
 673                 if (map[*ds]) {
 674                         switch(encoding) {
 675                         case ENCODING_REL_URI:
 676                         case ENCODING_REL_URI_PART:
 677                                 d_len += 3;
 678                                 break;
 679                         case ENCODING_HTML:
 680                         case ENCODING_MINIMAL_XML:
 681                                 d_len += 6;
 682                                 break;
 683                         case ENCODING_HTTP_HEADER:
 684                         case ENCODING_HEX:
 685                                 d_len += 2;
 686                                 break;
 687                         }
 688                 } else {
 689                         d_len++;
 690                 }
 691         }
 692
 693         d = (unsigned char*) buffer_string_prepare_append(b, d_len);
 694         buffer_commit(b, d_len); /* fill below */
 695         force_assert('\0' == *d);
 696
 697         for (ds = (unsigned char *)s, d_len = 0, ndx = 0; ndx < s_len; ds++, ndx++) {
 698                 if (map[*ds]) {
 699                         switch(encoding) {
 700                         case ENCODING_REL_URI:
 701                         case ENCODING_REL_URI_PART:
 702                                 d[d_len++] = '%';
 703                                 d[d_len++] = hex_chars[((*ds) >> 4) & 0x0F];
 704                                 d[d_len++] = hex_chars[(*ds) & 0x0F];
 705                                 break;
 706                         case ENCODING_HTML:
 707                         case ENCODING_MINIMAL_XML:
 708                                 d[d_len++] = '&';
 709                                 d[d_len++] = '#';
 710                                 d[d_len++] = 'x';
 711                                 d[d_len++] = hex_chars[((*ds) >> 4) & 0x0F];
 712                                 d[d_len++] = hex_chars[(*ds) & 0x0F];
 713                                 d[d_len++] = ';';
 714                                 break;
 715                         case ENCODING_HEX:
 716                                 d[d_len++] = hex_chars[((*ds) >> 4) & 0x0F];
 717                                 d[d_len++] = hex_chars[(*ds) & 0x0F];
 718                                 break;
 719                         case ENCODING_HTTP_HEADER:
 720                                 d[d_len++] = *ds;
 721                                 d[d_len++] = '\t';
 722                                 break;
 723                         }
 724                 } else {
 725                         d[d_len++] = *ds;
 726                 }
 727         }
 728 }
 729
 730 void buffer_append_string_c_escaped(buffer *b, const char *s, size_t s_len) {
 731         unsigned char *ds, *d;
 732         size_t d_len, ndx;
 733
 734         force_assert(NULL != b);
 735         force_assert(NULL != s || 0 == s_len);
 736
 737         if (0 == s_len) return;
 738
 739         /* count to-be-encoded-characters */
 740         for (ds = (unsigned char *)s, d_len = 0, ndx = 0; ndx < s_len; ds++, ndx++) {
 741                 if ((*ds < 0x20) /* control character */
 742                                 || (*ds >= 0x7f)) { /* DEL + non-ASCII characters */
 743                         switch (*ds) {
 744                         case '\t':
 745                         case '\r':
 746                         case '\n':
 747                                 d_len += 2;
 748                                 break;
 749                         default:
 750                                 d_len += 4; /* \xCC */
 751                                 break;
 752                         }
 753                 } else {
 754                         d_len++;
 755                 }
 756         }
 757
 758         d = (unsigned char*) buffer_string_prepare_append(b, d_len);
 759         buffer_commit(b, d_len); /* fill below */
 760         force_assert('\0' == *d);
 761
 762         for (ds = (unsigned char *)s, d_len = 0, ndx = 0; ndx < s_len; ds++, ndx++) {
 763                 if ((*ds < 0x20) /* control character */
 764                                 || (*ds >= 0x7f)) { /* DEL + non-ASCII characters */
 765                         d[d_len++] = '\\';
 766                         switch (*ds) {
 767                         case '\t':
 768                                 d[d_len++] = 't';
 769                                 break;
 770                         case '\r':
 771                                 d[d_len++] = 'r';
 772                                 break;
 773                         case '\n':
 774                                 d[d_len++] = 'n';
 775                                 break;
 776                         default:
 777                                 d[d_len++] = 'x';
 778                                 d[d_len++] = hex_chars[((*ds) >> 4) & 0x0F];
 779                                 d[d_len++] = hex_chars[(*ds) & 0x0F];
 780                                 break;
 781                         }
 782                 } else {
 783                         d[d_len++] = *ds;
 784                 }
 785         }
 786 }
 787
 788
 789 void buffer_copy_string_encoded_cgi_varnames(buffer *b, const char *s, size_t s_len, int is_http_header) {
 790         size_t i, j;
 791
 792         force_assert(NULL != b);
 793         force_assert(NULL != s || 0 == s_len);
 794
 795         buffer_reset(b);
 796
 797         if (is_http_header && NULL != s && 0 != strcasecmp(s, "CONTENT-TYPE")) {
 798                 buffer_string_prepare_append(b, s_len + 5);
 799                 buffer_copy_string_len(b, CONST_STR_LEN("HTTP_"));
 800         } else {
 801                 buffer_string_prepare_append(b, s_len);
 802         }
 803
 804         j = buffer_string_length(b);
 805         for (i = 0; i < s_len; ++i) {
 806                 unsigned char cr = s[i];
 807                 if (light_isalpha(cr)) {
 808                         /* upper-case */
 809                         cr &= ~32;
 810                 } else if (!light_isdigit(cr)) {
 811                         cr = '_';
 812                 }
 813                 b->ptr[j++] = cr;
 814         }
 815         b->used = j;
 816         b->ptr[b->used++] = '\0';
 817 }
 818
 819 /* decodes url-special-chars inplace.
 820  * replaces non-printable characters with '_'
 821  */
 822
 823 static void buffer_urldecode_internal(buffer *url, int is_query) {
 824         unsigned char high, low;
 825         char *src;
 826         char *dst;
 827
 828         force_assert(NULL != url);
 829         if (buffer_string_is_empty(url)) return;
 830
 831         force_assert('\0' == url->ptr[url->used-1]);
 832
 833         src = (char*) url->ptr;
 834
 835         while ('\0' != *src) {
 836                 if ('%' == *src) break;
 837                 if (is_query && '+' == *src) *src = ' ';
 838                 src++;
 839         }
 840         dst = src;
 841
 842         while ('\0' != *src) {
 843                 if (is_query && *src == '+') {
 844                         *dst = ' ';
 845                 } else if (*src == '%') {
 846                         *dst = '%';
 847
 848                         high = hex2int(*(src + 1));
 849                         if (0xFF != high) {
 850                                 low = hex2int(*(src + 2));
 851                                 if (0xFF != low) {
 852                                         high = (high << 4) | low;
 853
 854                                         /* map control-characters out */
 855                                         if (high < 32 || high == 127) high = '_';
 856
 857                                         *dst = high;
 858                                         src += 2;
 859                                 }
 860                         }
 861                 } else {
 862                         *dst = *src;
 863                 }
 864
 865                 dst++;
 866                 src++;
 867         }
 868
 869         *dst = '\0';
 870         url->used = (dst - url->ptr) + 1;
 871 }
 872
 873 void buffer_urldecode_path(buffer *url) {
 874         buffer_urldecode_internal(url, 0);
 875 }
 876
 877 void buffer_urldecode_query(buffer *url) {
 878         buffer_urldecode_internal(url, 1);
 879 }
 880
 881 /* - special case: empty string returns empty string
 882  * - on windows or cygwin: replace \ with /
 883  * - strip leading spaces
 884  * - prepends "/" if not present already
 885  * - resolve "/../", "//" and "/./" the usual way:
 886  *   the first one removes a preceding component, the other two
 887  *   get compressed to "/".
 888  * - "/." and "/.." at the end are similar, but always leave a trailing
 889  *   "/"
 890  *
 891  * /blah/..         gets  /
 892  * /blah/../foo     gets  /foo
 893  * /abc/./xyz       gets  /abc/xyz
 894  * /abc//xyz        gets  /abc/xyz
 895  *
 896  * NOTE: src and dest can point to the same buffer, in which case,
 897  *       the operation is performed in-place.
 898  */
 899
 900 void buffer_path_simplify(buffer *dest, buffer *src)
 901 {
 902         /* current character, the one before, and the one before that from input */
 903         char c, pre1, pre2;
 904         char *start, *slash, *walk, *out;
 905
 906         force_assert(NULL != dest && NULL != src);
 907
 908         if (buffer_string_is_empty(src)) {
 909                 buffer_string_prepare_copy(dest, 0);
 910                 return;
 911         }
 912
 913         force_assert('\0' == src->ptr[src->used-1]);
 914
 915         /* might need one character more for the '/' prefix */
 916         if (src == dest) {
 917                 buffer_string_prepare_append(dest, 1);
 918         } else {
 919                 buffer_string_prepare_copy(dest, buffer_string_length(src) + 1);
 920         }
 921
 922 #if defined(__WIN32) || defined(__CYGWIN__)
 923         /* cygwin is treating \ and / the same, so we have to that too */
 924         {
 925                 char *p;
 926                 for (p = src->ptr; *p; p++) {
 927                         if (*p == '\\') *p = '/';
 928                 }
 929         }
 930 #endif
 931
 932         walk  = src->ptr;
 933         start = dest->ptr;
 934         out   = dest->ptr;
 935         slash = dest->ptr;
 936
 937         /* skip leading spaces */
 938         while (*walk == ' ') {
 939                 walk++;
 940         }
 941
 942         pre2 = pre1 = 0;
 943         c = *(walk++);
 944         /* prefix with '/' if not already present */
 945         if (c != '/') {
 946                 pre1 = '/';
 947                 *(out++) = '/';
 948         }
 949
 950         while (c != '\0') {
 951                 /* assert((src != dest || out <= walk) && slash <= out); */
 952                 /* the following comments about out and walk are only interesting if
 953                  * src == dest; otherwise the memory areas don't overlap anyway.
 954                  */
 955                 pre2 = pre1;
 956                 pre1 = c;
 957
 958                 /* possibly: out == walk - need to read first */
 959                 c    = *walk;
 960                 *out = pre1;
 961
 962                 out++;
 963                 walk++;
 964                 /* (out <= walk) still true; also now (slash < out) */
 965
 966                 if (c == '/' || c == '\0') {
 967                         const size_t toklen = out - slash;
 968                         if (toklen == 3 && pre2 == '.' && pre1 == '.') {
 969                                 /* "/../" or ("/.." at end of string) */
 970                                 out = slash;
 971                                 /* if there is something before "/..", there is at least one
 972                                  * component, which needs to be removed */
 973                                 if (out > start) {
 974                                         out--;
 975                                         while (out > start && *out != '/') out--;
 976                                 }
 977
 978                                 /* don't kill trailing '/' at end of path */
 979                                 if (c == '\0') out++;
 980                                 /* slash < out before, so out_new <= slash + 1 <= out_before <= walk */
 981                         } else if (toklen == 1 || (pre2 == '/' && pre1 == '.')) {
 982                                 /* "//" or "/./" or (("/" or "/.") at end of string) */
 983                                 out = slash;
 984                                 /* don't kill trailing '/' at end of path */
 985                                 if (c == '\0') out++;
 986                                 /* slash < out before, so out_new <= slash + 1 <= out_before <= walk */
 987                         }
 988
 989                         slash = out;
 990                 }
 991         }
 992
 993         buffer_string_set_length(dest, out - start);
 994 }
 995
 996 int light_isdigit(int c) {
 997         return (c >= '0' && c <= '9');
 998 }
 999
1000 int light_isxdigit(int c) {
1001         if (light_isdigit(c)) return 1;
1002
1003         c |= 32;
1004         return (c >= 'a' && c <= 'f');
1005 }
1006
1007 int light_isalpha(int c) {
1008         c |= 32;
1009         return (c >= 'a' && c <= 'z');
1010 }
1011
1012 int light_isalnum(int c) {
1013         return light_isdigit(c) || light_isalpha(c);
1014 }
1015
1016 void buffer_to_lower(buffer *b) {
1017         size_t i;
1018
1019         for (i = 0; i < b->used; ++i) {
1020                 char c = b->ptr[i];
1021                 if (c >= 'A' && c <= 'Z') b->ptr[i] |= 0x20;
1022         }
1023 }
1024
1025
1026 void buffer_to_upper(buffer *b) {
1027         size_t i;
1028
1029         for (i = 0; i < b->used; ++i) {
1030                 char c = b->ptr[i];
1031                 if (c >= 'A' && c <= 'Z') b->ptr[i] &= ~0x20;
1032         }
1033 }
1034
1035 #ifdef HAVE_LIBUNWIND
1036 # define UNW_LOCAL_ONLY
1037 # include <libunwind.h>
1038
1039 void print_backtrace(FILE *file) {
1040         unw_cursor_t cursor;
1041         unw_context_t context;
1042         int ret;
1043         unsigned int frame = 0;
1044
1045         if (0 != (ret = unw_getcontext(&context))) goto error;
1046         if (0 != (ret = unw_init_local(&cursor, &context))) goto error;
1047
1048         fprintf(file, "Backtrace:\n");
1049
1050         while (0 < (ret = unw_step(&cursor))) {
1051                 unw_word_t proc_ip = 0;
1052                 unw_proc_info_t procinfo;
1053                 char procname[256];
1054                 unw_word_t proc_offset = 0;
1055
1056                 if (0 != (ret = unw_get_reg(&cursor, UNW_REG_IP, &proc_ip))) goto error;
1057
1058                 if (0 == proc_ip) {
1059                         /* without an IP the other functions are useless; unw_get_proc_name would return UNW_EUNSPEC */
1060                         ++frame;
1061                         fprintf(file, "%u: (nil)\n", frame);
1062                         continue;
1063                 }
1064
1065                 if (0 != (ret = unw_get_proc_info(&cursor, &procinfo))) goto error;
1066
1067                 if (0 != (ret = unw_get_proc_name(&cursor, procname, sizeof(procname), &proc_offset))) {
1068                         switch (-ret) {
1069                         case UNW_ENOMEM:
1070                                 memset(procname + sizeof(procname) - 4, '.', 3);
1071                                 procname[sizeof(procname) - 1] = '\0';
1072                                 break;
1073                         case UNW_ENOINFO:
1074                                 procname[0] = '?';
1075                                 procname[1] = '\0';
1076                                 proc_offset = 0;
1077                                 break;
1078                         default:
1079                                 snprintf(procname, sizeof(procname), "?? (unw_get_proc_name error %d)", -ret);
1080                                 break;
1081                         }
1082                 }
1083
1084                 ++frame;
1085                 fprintf(file, "%u: %s (+0x%x) [%p]\n",
1086                         frame,
1087                         procname,
1088                         (unsigned int) proc_offset,
1089                         (void*)(uintptr_t)proc_ip);
1090         }
1091
1092         if (0 != ret) goto error;
1093
1094         return;
1095
1096 error:
1097         fprintf(file, "Error while generating backtrace: unwind error %i\n", (int) -ret);
1098 }
1099 #else
1100 void print_backtrace(FILE *file) {
1101         UNUSED(file);
1102 }
1103 #endif
1104
1105 void log_failed_assert(const char *filename, unsigned int line, const char *msg) {
1106         /* can't use buffer here; could lead to recursive assertions */
1107         fprintf(stderr, "%s.%d: %s\n", filename, line, msg);
1108         print_backtrace(stderr);
1109         fflush(stderr);
1110         abort();
1111 }