hphp/zend/zend-string.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    | Copyright (c) 1998-2010 Zend Technologies Ltd. (http://www.zend.com) |
   7    +----------------------------------------------------------------------+
   8    | This source file is subject to version 2.00 of the Zend license,     |
   9    | that is bundled with this package in the file LICENSE, and is        |
  10    | available through the world-wide-web at the following url:           |
  11    | http://www.zend.com/license/2_00.txt.                                |
  12    | If you did not receive a copy of the Zend license and are unable to  |
  13    | obtain it through the world-wide-web, please send a note to          |
  14    | license@zend.com so we can mail you a copy immediately.              |
  15    +----------------------------------------------------------------------+
  16 */
  17
  18 #include "hphp/zend/zend-string.h"
  19
  20 #include <cinttypes>
  21
  22 #include "hphp/util/assertions.h"
  23 #include "hphp/util/mutex.h"
  24 #include "hphp/util/lock.h"
  25 #include "hphp/zend/crypt-blowfish.h"
  26
  27 #include <folly/portability/Unistd.h>
  28
  29 #if defined(_MSC_VER) || defined(__APPLE__)
  30 # include "hphp/zend/php-crypt_r.h"
  31 # define USE_PHP_CRYPT_R 1
  32 #else
  33 # include <crypt.h>
  34 #endif
  35
  36 namespace HPHP {
  37
  38 int string_copy(char *dst, const char *src, int siz) {
  39   register char *d = dst;
  40   register const char *s = src;
  41   register size_t n = siz;
  42
  43   /* Copy as many bytes as will fit */
  44   if (n != 0 && --n != 0) {
  45     do {
  46       if ((*d++ = *s++) == 0)
  47         break;
  48     } while (--n != 0);
  49   }
  50
  51   /* Not enough room in dst, add NUL and traverse rest of src */
  52   if (n == 0) {
  53     if (siz != 0)
  54       *d = '\0';    /* NUL-terminate dst */
  55     while (*s++)
  56       ;
  57   }
  58
  59   return(s - src - 1);  /* count does not include NUL */
  60 }
  61
  62 ///////////////////////////////////////////////////////////////////////////////
  63 // comparisons
  64
  65 int string_ncmp(const char *s1, const char *s2, int len) {
  66   for (int i = 0; i < len; i++) {
  67     char c1 = s1[i];
  68     char c2 = s2[i];
  69     if (c1 > c2) return 1;
  70     if (c1 < c2) return -1;
  71   }
  72   return 0;
  73 }
  74
  75 static int compare_right(char const **a, char const *aend,
  76                          char const **b, char const *bend) {
  77   int bias = 0;
  78
  79   /* The longest run of digits wins.  That aside, the greatest
  80      value wins, but we can't know that it will until we've scanned
  81      both numbers to know that they have the same magnitude, so we
  82      remember it in BIAS. */
  83   for(;; (*a)++, (*b)++) {
  84     if ((*a == aend || !isdigit((int)(unsigned char)**a)) &&
  85         (*b == bend || !isdigit((int)(unsigned char)**b)))
  86       return bias;
  87     else if (*a == aend || !isdigit((int)(unsigned char)**a))
  88       return -1;
  89     else if (*b == bend || !isdigit((int)(unsigned char)**b))
  90       return +1;
  91     else if (**a < **b) {
  92       if (!bias)
  93         bias = -1;
  94     } else if (**a > **b) {
  95       if (!bias)
  96         bias = +1;
  97     }
  98   }
  99
 100   return 0;
 101 }
 102
 103 static int compare_left(char const **a, char const *aend,
 104                         char const **b, char const *bend) {
 105   /* Compare two left-aligned numbers: the first to have a
 106      different value wins. */
 107   for(;; (*a)++, (*b)++) {
 108     if ((*a == aend || !isdigit((int)(unsigned char)**a)) &&
 109         (*b == bend || !isdigit((int)(unsigned char)**b)))
 110       return 0;
 111     else if (*a == aend || !isdigit((int)(unsigned char)**a))
 112       return -1;
 113     else if (*b == bend || !isdigit((int)(unsigned char)**b))
 114       return +1;
 115     else if (**a < **b)
 116       return -1;
 117     else if (**a > **b)
 118       return +1;
 119   }
 120
 121   return 0;
 122 }
 123
 124 int string_natural_cmp(char const *a, size_t a_len,
 125                        char const *b, size_t b_len, int fold_case) {
 126   char ca, cb;
 127   char const *ap, *bp;
 128   char const *aend = a + a_len, *bend = b + b_len;
 129   int fractional, result;
 130
 131   if (a_len == 0 || b_len == 0)
 132     return a_len - b_len;
 133
 134   ap = a;
 135   bp = b;
 136   while (1) {
 137     ca = *ap; cb = *bp;
 138
 139     /* skip over leading spaces or zeros */
 140     while (isspace((int)(unsigned char)ca))
 141       ca = *++ap;
 142
 143     while (isspace((int)(unsigned char)cb))
 144       cb = *++bp;
 145
 146     /* process run of digits */
 147     if (isdigit((int)(unsigned char)ca)  &&  isdigit((int)(unsigned char)cb)) {
 148       fractional = (ca == '0' || cb == '0');
 149
 150       if (fractional)
 151         result = compare_left(&ap, aend, &bp, bend);
 152       else
 153         result = compare_right(&ap, aend, &bp, bend);
 154
 155       if (result != 0)
 156         return result;
 157       else if (ap == aend && bp == bend)
 158         /* End of the strings. Let caller sort them out. */
 159         return 0;
 160       else {
 161         /* Keep on comparing from the current point. */
 162         ca = *ap; cb = *bp;
 163       }
 164     }
 165
 166     if (fold_case) {
 167       ca = toupper((int)(unsigned char)ca);
 168       cb = toupper((int)(unsigned char)cb);
 169     }
 170
 171     if (ca < cb)
 172       return -1;
 173     else if (ca > cb)
 174       return +1;
 175
 176     ++ap; ++bp;
 177     if (ap >= aend && bp >= bend)
 178       /* The strings compare the same.  Perhaps the caller
 179          will want to call strcmp to break the tie. */
 180       return 0;
 181     else if (ap >= aend)
 182       return -1;
 183     else if (bp >= bend)
 184       return 1;
 185   }
 186 }
 187
 188
 189 //////////////////////////////////////////////////////////////////////
 190
 191 void string_translate(char *str, int len, const char *str_from,
 192                       const char *str_to, int trlen) {
 193   int i;
 194   unsigned char xlat[256];
 195
 196   if ((trlen < 1) || (len < 1)) {
 197     return;
 198   }
 199
 200   for (i = 0; i < 256; xlat[i] = i, i++);
 201   for (i = 0; i < trlen; i++) {
 202     xlat[(unsigned char) str_from[i]] = str_to[i];
 203   }
 204
 205   for (i = 0; i < len; i++) {
 206     str[i] = xlat[(unsigned char) str[i]];
 207   }
 208 }
 209
 210 char *string_rot13(const char *input, int len) {
 211   assert(input);
 212
 213   static char rot13_from[] =
 214     "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
 215   static char rot13_to[] =
 216     "nopqrstuvwxyzabcdefghijklmNOPQRSTUVWXYZABCDEFGHIJKLM";
 217
 218   if (len == 0) {
 219     return nullptr;
 220   }
 221   char *ret = string_duplicate(input, len);
 222   string_translate(ret, len, rot13_from, rot13_to, 52);
 223   return ret;
 224 }
 225
 226 ///////////////////////////////////////////////////////////////////////////////
 227 // crc32
 228
 229 /*
 230  * This code implements the AUTODIN II polynomial
 231  * The variable corresponding to the macro argument "crc" should
 232  * be an unsigned long.
 233  * Original code  by Spencer Garrett <srg@quick.com>
 234  */
 235
 236 #define CRC32(crc, ch) (crc = (crc >> 8) ^ crc32tab[(crc ^ (ch)) & 0xff])
 237
 238 /* generated using the AUTODIN II polynomial
 239  *  x^32 + x^26 + x^23 + x^22 + x^16 +
 240  *  x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x^1 + 1
 241  */
 242 static const unsigned int crc32tab[256] = {
 243   0x00000000, 0x77073096, 0xee0e612c, 0x990951ba,
 244   0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,
 245   0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
 246   0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,
 247   0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
 248   0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
 249   0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,
 250   0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,
 251   0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
 252   0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
 253   0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940,
 254   0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
 255   0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116,
 256   0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
 257   0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
 258   0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,
 259   0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a,
 260   0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
 261   0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818,
 262   0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
 263   0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
 264   0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,
 265   0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c,
 266   0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
 267   0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
 268   0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,
 269   0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
 270   0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
 271   0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086,
 272   0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
 273   0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4,
 274   0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,
 275   0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
 276   0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,
 277   0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
 278   0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
 279   0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe,
 280   0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,
 281   0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
 282   0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
 283   0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252,
 284   0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
 285   0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60,
 286   0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,
 287   0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
 288   0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,
 289   0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04,
 290   0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
 291   0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a,
 292   0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
 293   0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
 294   0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,
 295   0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e,
 296   0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
 297   0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
 298   0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
 299   0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
 300   0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,
 301   0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0,
 302   0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
 303   0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6,
 304   0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,
 305   0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
 306   0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d,
 307 };
 308
 309 int string_crc32(const char *p, int len) {
 310   uint32_t crcinit = 0;
 311   register int32_t crc = crcinit ^ 0xFFFFFFFF;
 312   for (; len--; ++p) {
 313     crc = ((crc >> 8) & 0x00FFFFFF) ^ crc32tab[(crc ^ (*p)) & 0xFF];
 314   }
 315   return crc ^ 0xFFFFFFFF;
 316 }
 317
 318 ///////////////////////////////////////////////////////////////////////////////
 319 // crypt
 320
 321 #ifdef USE_PHP_CRYPT_R
 322
 323 char* php_crypt_r(const char* key, const char* salt) {
 324   if (salt[0] == '$' && salt[1] == '1' && salt[2] == '$') {
 325     char output[MD5_HASH_MAX_LEN], *out;
 326
 327     out = php_md5_crypt_r(key, salt, output);
 328     return out ? strdup(out) : nullptr;
 329   } else if (salt[0] == '$' && salt[1] == '6' && salt[2] == '$') {
 330     char output[PHP_MAX_SALT_LEN + 1];
 331
 332     char* crypt_res = php_sha512_crypt_r(key, salt, output, PHP_MAX_SALT_LEN);
 333     if (!crypt_res) {
 334       SECURE_ZERO(output, PHP_MAX_SALT_LEN + 1);
 335       return nullptr;
 336     } else {
 337       char* result = strdup(output);
 338       SECURE_ZERO(output, PHP_MAX_SALT_LEN + 1);
 339       return result;
 340     }
 341   } else if (salt[0] == '$' && salt[1] == '5' && salt[2] == '$') {
 342     char output[PHP_MAX_SALT_LEN + 1];
 343
 344     char* crypt_res = php_sha256_crypt_r(key, salt, output, PHP_MAX_SALT_LEN);
 345     if (!crypt_res) {
 346       SECURE_ZERO(output, PHP_MAX_SALT_LEN + 1);
 347       return nullptr;
 348     } else {
 349       char* result = strdup(output);
 350       SECURE_ZERO(output, PHP_MAX_SALT_LEN + 1);
 351       return result;
 352     }
 353   } else if (
 354     salt[0] == '$' &&
 355     salt[1] == '2' &&
 356     salt[3] == '$') {
 357     char output[PHP_MAX_SALT_LEN + 1];
 358
 359     memset(output, 0, PHP_MAX_SALT_LEN + 1);
 360
 361     char* crypt_res = php_crypt_blowfish_rn(key, salt, output, sizeof(output));
 362     if (!crypt_res) {
 363       SECURE_ZERO(output, PHP_MAX_SALT_LEN + 1);
 364       return nullptr;
 365     } else {
 366       char* result = strdup(output);
 367       SECURE_ZERO(output, PHP_MAX_SALT_LEN + 1);
 368       return result;
 369     }
 370   } else if (salt[0] == '*' && (salt[1] == '0' || salt[1] == '1')) {
 371     return nullptr;
 372   } else {
 373     struct php_crypt_extended_data buffer;
 374     /* DES Fallback */
 375     memset(&buffer, 0, sizeof(buffer));
 376     _crypt_extended_init_r();
 377
 378     char* crypt_res = _crypt_extended_r(key, salt, &buffer);
 379     if (!crypt_res || (salt[0] == '*' && salt[1] == '0')) {
 380       return nullptr;
 381     } else {
 382       return strdup(crypt_res);
 383     }
 384   }
 385 }
 386
 387 #endif
 388
 389 static unsigned char itoa64[] =
 390   "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
 391 static void ito64(char *s, long v, int n) {
 392   while (--n >= 0) {
 393     *s++ = itoa64[v&0x3f];
 394     v >>= 6;
 395   }
 396 }
 397
 398 char *string_crypt(const char *key, const char *salt) {
 399   assertx(key);
 400   assertx(salt);
 401
 402   char random_salt[12];
 403   if (!*salt) {
 404     memcpy(random_salt,"$1$",3);
 405     ito64(random_salt+3,rand(),8);
 406     random_salt[11] = '\0';
 407     return string_crypt(key, random_salt);
 408   }
 409
 410   auto const saltLen = strlen(salt);
 411   if ((saltLen > sizeof("$2X$00$")) &&
 412     (salt[0] == '$') &&
 413     (salt[1] == '2') &&
 414     (salt[2] >= 'a') && (salt[2] <= 'z') &&
 415     (salt[3] == '$') &&
 416     (salt[4] >= '0') && (salt[4] <= '3') &&
 417     (salt[5] >= '0') && (salt[5] <= '9') &&
 418     (salt[6] == '$')) {
 419     // Bundled blowfish crypt()
 420     char output[61];
 421
 422     static constexpr size_t maxSaltLength = 123;
 423     char paddedSalt[maxSaltLength + 1];
 424     paddedSalt[0] = paddedSalt[maxSaltLength] = '\0';
 425
 426     memset(&paddedSalt[1], '$', maxSaltLength - 1);
 427     memcpy(paddedSalt, salt, std::min(maxSaltLength, saltLen));
 428     paddedSalt[std::min(maxSaltLength, saltLen)] = '\0';
 429
 430     if (php_crypt_blowfish_rn(key, paddedSalt, output, sizeof(output))) {
 431       return strdup(output);
 432     }
 433
 434   } else {
 435     // System crypt() function
 436 #ifdef USE_PHP_CRYPT_R
 437     return php_crypt_r(key, salt);
 438 #else
 439     static Mutex mutex;
 440     Lock lock(mutex);
 441     char *crypt_res = crypt(key,salt);
 442
 443     if (crypt_res) {
 444       return strdup(crypt_res);
 445     }
 446 #endif
 447   }
 448
 449   return ((salt[0] == '*') && (salt[1] == '0'))
 450                   ? strdup("*1") : strdup("*0");
 451 }
 452
 453 //////////////////////////////////////////////////////////////////////
 454
 455 char *string_bin2hex(const char *input, int len, char* result) {
 456   static char hexconvtab[] = "0123456789abcdef";
 457
 458   assert(input);
 459   if (len == 0) {
 460     return nullptr;
 461   }
 462
 463   int i, j;
 464   for (i = j = 0; i < len; i++) {
 465     result[j++] = hexconvtab[(unsigned char)input[i] >> 4];
 466     result[j++] = hexconvtab[(unsigned char)input[i] & 15];
 467   }
 468   result[j] = '\0';
 469   return result;
 470 }
 471
 472 char *string_bin2hex(const char *input, int &len) {
 473   if (!len) return nullptr;
 474   int inLen = len;
 475   int outLen = inLen * 2;
 476   char* result = (char*)malloc(outLen + 1);
 477   len = outLen;
 478   return string_bin2hex(input, inLen, result);
 479 }
 480
 481 //////////////////////////////////////////////////////////////////////
 482
 483 }