granicus.if.org Git - postgresql/blob - src/backend/utils/adt/varbit.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * varbit.c
   4  *        Functions for the SQL datatypes BIT() and BIT VARYING().
   5  *
   6  * Code originally contributed by Adriaan Joubert.
   7  *
   8  * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
   9  * Portions Copyright (c) 1994, Regents of the University of California
  10  *
  11  * IDENTIFICATION
  12  *        src/backend/utils/adt/varbit.c
  13  *
  14  *-------------------------------------------------------------------------
  15  */
  16
  17 #include "postgres.h"
  18
  19 #include "access/htup_details.h"
  20 #include "libpq/pqformat.h"
  21 #include "nodes/nodeFuncs.h"
  22 #include "utils/array.h"
  23 #include "utils/builtins.h"
  24 #include "utils/varbit.h"
  25
  26 #define HEXDIG(z)        ((z)<10 ? ((z)+'0') : ((z)-10+'A'))
  27
  28 static VarBit *bit_catenate(VarBit *arg1, VarBit *arg2);
  29 static VarBit *bitsubstring(VarBit *arg, int32 s, int32 l,
  30                          bool length_not_specified);
  31 static VarBit *bit_overlay(VarBit *t1, VarBit *t2, int sp, int sl);
  32
  33
  34 /*
  35  * common code for bittypmodin and varbittypmodin
  36  */
  37 static int32
  38 anybit_typmodin(ArrayType *ta, const char *typename)
  39 {
  40         int32           typmod;
  41         int32      *tl;
  42         int                     n;
  43
  44         tl = ArrayGetIntegerTypmods(ta, &n);
  45
  46         /*
  47          * we're not too tense about good error message here because grammar
  48          * shouldn't allow wrong number of modifiers for BIT
  49          */
  50         if (n != 1)
  51                 ereport(ERROR,
  52                                 (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
  53                                  errmsg("invalid type modifier")));
  54
  55         if (*tl < 1)
  56                 ereport(ERROR,
  57                                 (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
  58                                  errmsg("length for type %s must be at least 1",
  59                                                 typename)));
  60         if (*tl > (MaxAttrSize * BITS_PER_BYTE))
  61                 ereport(ERROR,
  62                                 (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
  63                                  errmsg("length for type %s cannot exceed %d",
  64                                                 typename, MaxAttrSize * BITS_PER_BYTE)));
  65
  66         typmod = *tl;
  67
  68         return typmod;
  69 }
  70
  71 /*
  72  * common code for bittypmodout and varbittypmodout
  73  */
  74 static char *
  75 anybit_typmodout(int32 typmod)
  76 {
  77         char       *res = (char *) palloc(64);
  78
  79         if (typmod >= 0)
  80                 snprintf(res, 64, "(%d)", typmod);
  81         else
  82                 *res = '\0';
  83
  84         return res;
  85 }
  86
  87
  88 /*----------
  89  *      attypmod -- contains the length of the bit string in bits, or for
  90  *                         varying bits the maximum length.
  91  *
  92  *      The data structure contains the following elements:
  93  *        header  -- length of the whole data structure (incl header)
  94  *                               in bytes. (as with all varying length datatypes)
  95  *        data section -- private data section for the bits data structures
  96  *              bitlength -- length of the bit string in bits
  97  *              bitdata   -- bit string, most significant byte first
  98  *
  99  *      The length of the bitdata vector should always be exactly as many
 100  *      bytes as are needed for the given bitlength.  If the bitlength is
 101  *      not a multiple of 8, the extra low-order padding bits of the last
 102  *      byte must be zeroes.
 103  *----------
 104  */
 105
 106 /*
 107  * bit_in -
 108  *        converts a char string to the internal representation of a bitstring.
 109  *                The length is determined by the number of bits required plus
 110  *                VARHDRSZ bytes or from atttypmod.
 111  */
 112 Datum
 113 bit_in(PG_FUNCTION_ARGS)
 114 {
 115         char       *input_string = PG_GETARG_CSTRING(0);
 116
 117 #ifdef NOT_USED
 118         Oid                     typelem = PG_GETARG_OID(1);
 119 #endif
 120         int32           atttypmod = PG_GETARG_INT32(2);
 121         VarBit     *result;                     /* The resulting bit string                       */
 122         char       *sp;                         /* pointer into the character string  */
 123         bits8      *r;                          /* pointer into the result */
 124         int                     len,                    /* Length of the whole data structure */
 125                                 bitlen,                 /* Number of bits in the bit string   */
 126                                 slen;                   /* Length of the input string             */
 127         bool            bit_not_hex;    /* false = hex string  true = bit string */
 128         int                     bc;
 129         bits8           x = 0;
 130
 131         /* Check that the first character is a b or an x */
 132         if (input_string[0] == 'b' || input_string[0] == 'B')
 133         {
 134                 bit_not_hex = true;
 135                 sp = input_string + 1;
 136         }
 137         else if (input_string[0] == 'x' || input_string[0] == 'X')
 138         {
 139                 bit_not_hex = false;
 140                 sp = input_string + 1;
 141         }
 142         else
 143         {
 144                 /*
 145                  * Otherwise it's binary.  This allows things like cast('1001' as bit)
 146                  * to work transparently.
 147                  */
 148                 bit_not_hex = true;
 149                 sp = input_string;
 150         }
 151
 152         /*
 153          * Determine bitlength from input string.  MaxAllocSize ensures a regular
 154          * input is small enough, but we must check hex input.
 155          */
 156         slen = strlen(sp);
 157         if (bit_not_hex)
 158                 bitlen = slen;
 159         else
 160         {
 161                 if (slen > VARBITMAXLEN / 4)
 162                         ereport(ERROR,
 163                                         (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
 164                                  errmsg("bit string length exceeds the maximum allowed (%d)",
 165                                                 VARBITMAXLEN)));
 166                 bitlen = slen * 4;
 167         }
 168
 169         /*
 170          * Sometimes atttypmod is not supplied. If it is supplied we need to make
 171          * sure that the bitstring fits.
 172          */
 173         if (atttypmod <= 0)
 174                 atttypmod = bitlen;
 175         else if (bitlen != atttypmod)
 176                 ereport(ERROR,
 177                                 (errcode(ERRCODE_STRING_DATA_LENGTH_MISMATCH),
 178                                  errmsg("bit string length %d does not match type bit(%d)",
 179                                                 bitlen, atttypmod)));
 180
 181         len = VARBITTOTALLEN(atttypmod);
 182         /* set to 0 so that *r is always initialised and string is zero-padded */
 183         result = (VarBit *) palloc0(len);
 184         SET_VARSIZE(result, len);
 185         VARBITLEN(result) = atttypmod;
 186
 187         r = VARBITS(result);
 188         if (bit_not_hex)
 189         {
 190                 /* Parse the bit representation of the string */
 191                 /* We know it fits, as bitlen was compared to atttypmod */
 192                 x = HIGHBIT;
 193                 for (; *sp; sp++)
 194                 {
 195                         if (*sp == '1')
 196                                 *r |= x;
 197                         else if (*sp != '0')
 198                                 ereport(ERROR,
 199                                                 (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
 200                                                  errmsg("\"%c\" is not a valid binary digit",
 201                                                                 *sp)));
 202
 203                         x >>= 1;
 204                         if (x == 0)
 205                         {
 206                                 x = HIGHBIT;
 207                                 r++;
 208                         }
 209                 }
 210         }
 211         else
 212         {
 213                 /* Parse the hex representation of the string */
 214                 for (bc = 0; *sp; sp++)
 215                 {
 216                         if (*sp >= '0' && *sp <= '9')
 217                                 x = (bits8) (*sp - '0');
 218                         else if (*sp >= 'A' && *sp <= 'F')
 219                                 x = (bits8) (*sp - 'A') + 10;
 220                         else if (*sp >= 'a' && *sp <= 'f')
 221                                 x = (bits8) (*sp - 'a') + 10;
 222                         else
 223                                 ereport(ERROR,
 224                                                 (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
 225                                                  errmsg("\"%c\" is not a valid hexadecimal digit",
 226                                                                 *sp)));
 227
 228                         if (bc)
 229                         {
 230                                 *r++ |= x;
 231                                 bc = 0;
 232                         }
 233                         else
 234                         {
 235                                 *r = x << 4;
 236                                 bc = 1;
 237                         }
 238                 }
 239         }
 240
 241         PG_RETURN_VARBIT_P(result);
 242 }
 243
 244
 245 Datum
 246 bit_out(PG_FUNCTION_ARGS)
 247 {
 248 #if 1
 249         /* same as varbit output */
 250         return varbit_out(fcinfo);
 251 #else
 252
 253         /*
 254          * This is how one would print a hex string, in case someone wants to
 255          * write a formatting function.
 256          */
 257         VarBit     *s = PG_GETARG_VARBIT_P(0);
 258         char       *result,
 259                            *r;
 260         bits8      *sp;
 261         int                     i,
 262                                 len,
 263                                 bitlen;
 264
 265         bitlen = VARBITLEN(s);
 266         len = (bitlen + 3) / 4;
 267         result = (char *) palloc(len + 2);
 268         sp = VARBITS(s);
 269         r = result;
 270         *r++ = 'X';
 271         /* we cheat by knowing that we store full bytes zero padded */
 272         for (i = 0; i < len; i += 2, sp++)
 273         {
 274                 *r++ = HEXDIG((*sp) >> 4);
 275                 *r++ = HEXDIG((*sp) & 0xF);
 276         }
 277
 278         /*
 279          * Go back one step if we printed a hex number that was not part of the
 280          * bitstring anymore
 281          */
 282         if (i > len)
 283                 r--;
 284         *r = '\0';
 285
 286         PG_RETURN_CSTRING(result);
 287 #endif
 288 }
 289
 290 /*
 291  *              bit_recv                        - converts external binary format to bit
 292  */
 293 Datum
 294 bit_recv(PG_FUNCTION_ARGS)
 295 {
 296         StringInfo      buf = (StringInfo) PG_GETARG_POINTER(0);
 297
 298 #ifdef NOT_USED
 299         Oid                     typelem = PG_GETARG_OID(1);
 300 #endif
 301         int32           atttypmod = PG_GETARG_INT32(2);
 302         VarBit     *result;
 303         int                     len,
 304                                 bitlen;
 305         int                     ipad;
 306         bits8           mask;
 307
 308         bitlen = pq_getmsgint(buf, sizeof(int32));
 309         if (bitlen < 0 || bitlen > VARBITMAXLEN)
 310                 ereport(ERROR,
 311                                 (errcode(ERRCODE_INVALID_BINARY_REPRESENTATION),
 312                                  errmsg("invalid length in external bit string")));
 313
 314         /*
 315          * Sometimes atttypmod is not supplied. If it is supplied we need to make
 316          * sure that the bitstring fits.
 317          */
 318         if (atttypmod > 0 && bitlen != atttypmod)
 319                 ereport(ERROR,
 320                                 (errcode(ERRCODE_STRING_DATA_LENGTH_MISMATCH),
 321                                  errmsg("bit string length %d does not match type bit(%d)",
 322                                                 bitlen, atttypmod)));
 323
 324         len = VARBITTOTALLEN(bitlen);
 325         result = (VarBit *) palloc(len);
 326         SET_VARSIZE(result, len);
 327         VARBITLEN(result) = bitlen;
 328
 329         pq_copymsgbytes(buf, (char *) VARBITS(result), VARBITBYTES(result));
 330
 331         /* Make sure last byte is zero-padded if needed */
 332         ipad = VARBITPAD(result);
 333         if (ipad > 0)
 334         {
 335                 mask = BITMASK << ipad;
 336                 *(VARBITS(result) + VARBITBYTES(result) - 1) &= mask;
 337         }
 338
 339         PG_RETURN_VARBIT_P(result);
 340 }
 341
 342 /*
 343  *              bit_send                        - converts bit to binary format
 344  */
 345 Datum
 346 bit_send(PG_FUNCTION_ARGS)
 347 {
 348         /* Exactly the same as varbit_send, so share code */
 349         return varbit_send(fcinfo);
 350 }
 351
 352 /*
 353  * bit()
 354  * Converts a bit() type to a specific internal length.
 355  * len is the bitlength specified in the column definition.
 356  *
 357  * If doing implicit cast, raise error when source data is wrong length.
 358  * If doing explicit cast, silently truncate or zero-pad to specified length.
 359  */
 360 Datum
 361 bit(PG_FUNCTION_ARGS)
 362 {
 363         VarBit     *arg = PG_GETARG_VARBIT_P(0);
 364         int32           len = PG_GETARG_INT32(1);
 365         bool            isExplicit = PG_GETARG_BOOL(2);
 366         VarBit     *result;
 367         int                     rlen;
 368         int                     ipad;
 369         bits8           mask;
 370
 371         /* No work if typmod is invalid or supplied data matches it already */
 372         if (len <= 0 || len > VARBITMAXLEN || len == VARBITLEN(arg))
 373                 PG_RETURN_VARBIT_P(arg);
 374
 375         if (!isExplicit)
 376                 ereport(ERROR,
 377                                 (errcode(ERRCODE_STRING_DATA_LENGTH_MISMATCH),
 378                                  errmsg("bit string length %d does not match type bit(%d)",
 379                                                 VARBITLEN(arg), len)));
 380
 381         rlen = VARBITTOTALLEN(len);
 382         /* set to 0 so that string is zero-padded */
 383         result = (VarBit *) palloc0(rlen);
 384         SET_VARSIZE(result, rlen);
 385         VARBITLEN(result) = len;
 386
 387         memcpy(VARBITS(result), VARBITS(arg),
 388                    Min(VARBITBYTES(result), VARBITBYTES(arg)));
 389
 390         /*
 391          * Make sure last byte is zero-padded if needed.  This is useless but safe
 392          * if source data was shorter than target length (we assume the last byte
 393          * of the source data was itself correctly zero-padded).
 394          */
 395         ipad = VARBITPAD(result);
 396         if (ipad > 0)
 397         {
 398                 mask = BITMASK << ipad;
 399                 *(VARBITS(result) + VARBITBYTES(result) - 1) &= mask;
 400         }
 401
 402         PG_RETURN_VARBIT_P(result);
 403 }
 404
 405 Datum
 406 bittypmodin(PG_FUNCTION_ARGS)
 407 {
 408         ArrayType  *ta = PG_GETARG_ARRAYTYPE_P(0);
 409
 410         PG_RETURN_INT32(anybit_typmodin(ta, "bit"));
 411 }
 412
 413 Datum
 414 bittypmodout(PG_FUNCTION_ARGS)
 415 {
 416         int32           typmod = PG_GETARG_INT32(0);
 417
 418         PG_RETURN_CSTRING(anybit_typmodout(typmod));
 419 }
 420
 421
 422 /*
 423  * varbit_in -
 424  *        converts a string to the internal representation of a bitstring.
 425  *              This is the same as bit_in except that atttypmod is taken as
 426  *              the maximum length, not the exact length to force the bitstring to.
 427  */
 428 Datum
 429 varbit_in(PG_FUNCTION_ARGS)
 430 {
 431         char       *input_string = PG_GETARG_CSTRING(0);
 432
 433 #ifdef NOT_USED
 434         Oid                     typelem = PG_GETARG_OID(1);
 435 #endif
 436         int32           atttypmod = PG_GETARG_INT32(2);
 437         VarBit     *result;                     /* The resulting bit string                       */
 438         char       *sp;                         /* pointer into the character string  */
 439         bits8      *r;                          /* pointer into the result */
 440         int                     len,                    /* Length of the whole data structure */
 441                                 bitlen,                 /* Number of bits in the bit string   */
 442                                 slen;                   /* Length of the input string             */
 443         bool            bit_not_hex;    /* false = hex string  true = bit string */
 444         int                     bc;
 445         bits8           x = 0;
 446
 447         /* Check that the first character is a b or an x */
 448         if (input_string[0] == 'b' || input_string[0] == 'B')
 449         {
 450                 bit_not_hex = true;
 451                 sp = input_string + 1;
 452         }
 453         else if (input_string[0] == 'x' || input_string[0] == 'X')
 454         {
 455                 bit_not_hex = false;
 456                 sp = input_string + 1;
 457         }
 458         else
 459         {
 460                 bit_not_hex = true;
 461                 sp = input_string;
 462         }
 463
 464         /*
 465          * Determine bitlength from input string.  MaxAllocSize ensures a regular
 466          * input is small enough, but we must check hex input.
 467          */
 468         slen = strlen(sp);
 469         if (bit_not_hex)
 470                 bitlen = slen;
 471         else
 472         {
 473                 if (slen > VARBITMAXLEN / 4)
 474                         ereport(ERROR,
 475                                         (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
 476                                  errmsg("bit string length exceeds the maximum allowed (%d)",
 477                                                 VARBITMAXLEN)));
 478                 bitlen = slen * 4;
 479         }
 480
 481         /*
 482          * Sometimes atttypmod is not supplied. If it is supplied we need to make
 483          * sure that the bitstring fits.
 484          */
 485         if (atttypmod <= 0)
 486                 atttypmod = bitlen;
 487         else if (bitlen > atttypmod)
 488                 ereport(ERROR,
 489                                 (errcode(ERRCODE_STRING_DATA_RIGHT_TRUNCATION),
 490                                  errmsg("bit string too long for type bit varying(%d)",
 491                                                 atttypmod)));
 492
 493         len = VARBITTOTALLEN(bitlen);
 494         /* set to 0 so that *r is always initialised and string is zero-padded */
 495         result = (VarBit *) palloc0(len);
 496         SET_VARSIZE(result, len);
 497         VARBITLEN(result) = Min(bitlen, atttypmod);
 498
 499         r = VARBITS(result);
 500         if (bit_not_hex)
 501         {
 502                 /* Parse the bit representation of the string */
 503                 /* We know it fits, as bitlen was compared to atttypmod */
 504                 x = HIGHBIT;
 505                 for (; *sp; sp++)
 506                 {
 507                         if (*sp == '1')
 508                                 *r |= x;
 509                         else if (*sp != '0')
 510                                 ereport(ERROR,
 511                                                 (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
 512                                                  errmsg("\"%c\" is not a valid binary digit",
 513                                                                 *sp)));
 514
 515                         x >>= 1;
 516                         if (x == 0)
 517                         {
 518                                 x = HIGHBIT;
 519                                 r++;
 520                         }
 521                 }
 522         }
 523         else
 524         {
 525                 /* Parse the hex representation of the string */
 526                 for (bc = 0; *sp; sp++)
 527                 {
 528                         if (*sp >= '0' && *sp <= '9')
 529                                 x = (bits8) (*sp - '0');
 530                         else if (*sp >= 'A' && *sp <= 'F')
 531                                 x = (bits8) (*sp - 'A') + 10;
 532                         else if (*sp >= 'a' && *sp <= 'f')
 533                                 x = (bits8) (*sp - 'a') + 10;
 534                         else
 535                                 ereport(ERROR,
 536                                                 (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
 537                                                  errmsg("\"%c\" is not a valid hexadecimal digit",
 538                                                                 *sp)));
 539
 540                         if (bc)
 541                         {
 542                                 *r++ |= x;
 543                                 bc = 0;
 544                         }
 545                         else
 546                         {
 547                                 *r = x << 4;
 548                                 bc = 1;
 549                         }
 550                 }
 551         }
 552
 553         PG_RETURN_VARBIT_P(result);
 554 }
 555
 556 /*
 557  * varbit_out -
 558  *        Prints the string as bits to preserve length accurately
 559  *
 560  * XXX varbit_recv() and hex input to varbit_in() can load a value that this
 561  * cannot emit.  Consider using hex output for such values.
 562  */
 563 Datum
 564 varbit_out(PG_FUNCTION_ARGS)
 565 {
 566         VarBit     *s = PG_GETARG_VARBIT_P(0);
 567         char       *result,
 568                            *r;
 569         bits8      *sp;
 570         bits8           x;
 571         int                     i,
 572                                 k,
 573                                 len;
 574
 575         len = VARBITLEN(s);
 576         result = (char *) palloc(len + 1);
 577         sp = VARBITS(s);
 578         r = result;
 579         for (i = 0; i <= len - BITS_PER_BYTE; i += BITS_PER_BYTE, sp++)
 580         {
 581                 /* print full bytes */
 582                 x = *sp;
 583                 for (k = 0; k < BITS_PER_BYTE; k++)
 584                 {
 585                         *r++ = IS_HIGHBIT_SET(x) ? '1' : '0';
 586                         x <<= 1;
 587                 }
 588         }
 589         if (i < len)
 590         {
 591                 /* print the last partial byte */
 592                 x = *sp;
 593                 for (k = i; k < len; k++)
 594                 {
 595                         *r++ = IS_HIGHBIT_SET(x) ? '1' : '0';
 596                         x <<= 1;
 597                 }
 598         }
 599         *r = '\0';
 600
 601         PG_RETURN_CSTRING(result);
 602 }
 603
 604 /*
 605  *              varbit_recv                     - converts external binary format to varbit
 606  *
 607  * External format is the bitlen as an int32, then the byte array.
 608  */
 609 Datum
 610 varbit_recv(PG_FUNCTION_ARGS)
 611 {
 612         StringInfo      buf = (StringInfo) PG_GETARG_POINTER(0);
 613
 614 #ifdef NOT_USED
 615         Oid                     typelem = PG_GETARG_OID(1);
 616 #endif
 617         int32           atttypmod = PG_GETARG_INT32(2);
 618         VarBit     *result;
 619         int                     len,
 620                                 bitlen;
 621         int                     ipad;
 622         bits8           mask;
 623
 624         bitlen = pq_getmsgint(buf, sizeof(int32));
 625         if (bitlen < 0 || bitlen > VARBITMAXLEN)
 626                 ereport(ERROR,
 627                                 (errcode(ERRCODE_INVALID_BINARY_REPRESENTATION),
 628                                  errmsg("invalid length in external bit string")));
 629
 630         /*
 631          * Sometimes atttypmod is not supplied. If it is supplied we need to make
 632          * sure that the bitstring fits.
 633          */
 634         if (atttypmod > 0 && bitlen > atttypmod)
 635                 ereport(ERROR,
 636                                 (errcode(ERRCODE_STRING_DATA_RIGHT_TRUNCATION),
 637                                  errmsg("bit string too long for type bit varying(%d)",
 638                                                 atttypmod)));
 639
 640         len = VARBITTOTALLEN(bitlen);
 641         result = (VarBit *) palloc(len);
 642         SET_VARSIZE(result, len);
 643         VARBITLEN(result) = bitlen;
 644
 645         pq_copymsgbytes(buf, (char *) VARBITS(result), VARBITBYTES(result));
 646
 647         /* Make sure last byte is zero-padded if needed */
 648         ipad = VARBITPAD(result);
 649         if (ipad > 0)
 650         {
 651                 mask = BITMASK << ipad;
 652                 *(VARBITS(result) + VARBITBYTES(result) - 1) &= mask;
 653         }
 654
 655         PG_RETURN_VARBIT_P(result);
 656 }
 657
 658 /*
 659  *              varbit_send                     - converts varbit to binary format
 660  */
 661 Datum
 662 varbit_send(PG_FUNCTION_ARGS)
 663 {
 664         VarBit     *s = PG_GETARG_VARBIT_P(0);
 665         StringInfoData buf;
 666
 667         pq_begintypsend(&buf);
 668         pq_sendint(&buf, VARBITLEN(s), sizeof(int32));
 669         pq_sendbytes(&buf, (char *) VARBITS(s), VARBITBYTES(s));
 670         PG_RETURN_BYTEA_P(pq_endtypsend(&buf));
 671 }
 672
 673 /*
 674  * varbit_transform()
 675  * Flatten calls to varbit's length coercion function that set the new maximum
 676  * length >= the previous maximum length.  We can ignore the isExplicit
 677  * argument, since that only affects truncation cases.
 678  */
 679 Datum
 680 varbit_transform(PG_FUNCTION_ARGS)
 681 {
 682         FuncExpr   *expr = castNode(FuncExpr, PG_GETARG_POINTER(0));
 683         Node       *ret = NULL;
 684         Node       *typmod;
 685
 686         Assert(list_length(expr->args) >= 2);
 687
 688         typmod = (Node *) lsecond(expr->args);
 689
 690         if (IsA(typmod, Const) &&!((Const *) typmod)->constisnull)
 691         {
 692                 Node       *source = (Node *) linitial(expr->args);
 693                 int32           new_typmod = DatumGetInt32(((Const *) typmod)->constvalue);
 694                 int32           old_max = exprTypmod(source);
 695                 int32           new_max = new_typmod;
 696
 697                 /* Note: varbit() treats typmod 0 as invalid, so we do too */
 698                 if (new_max <= 0 || (old_max > 0 && old_max <= new_max))
 699                         ret = relabel_to_typmod(source, new_typmod);
 700         }
 701
 702         PG_RETURN_POINTER(ret);
 703 }
 704
 705 /*
 706  * varbit()
 707  * Converts a varbit() type to a specific internal length.
 708  * len is the maximum bitlength specified in the column definition.
 709  *
 710  * If doing implicit cast, raise error when source data is too long.
 711  * If doing explicit cast, silently truncate to max length.
 712  */
 713 Datum
 714 varbit(PG_FUNCTION_ARGS)
 715 {
 716         VarBit     *arg = PG_GETARG_VARBIT_P(0);
 717         int32           len = PG_GETARG_INT32(1);
 718         bool            isExplicit = PG_GETARG_BOOL(2);
 719         VarBit     *result;
 720         int                     rlen;
 721         int                     ipad;
 722         bits8           mask;
 723
 724         /* No work if typmod is invalid or supplied data matches it already */
 725         if (len <= 0 || len >= VARBITLEN(arg))
 726                 PG_RETURN_VARBIT_P(arg);
 727
 728         if (!isExplicit)
 729                 ereport(ERROR,
 730                                 (errcode(ERRCODE_STRING_DATA_RIGHT_TRUNCATION),
 731                                  errmsg("bit string too long for type bit varying(%d)",
 732                                                 len)));
 733
 734         rlen = VARBITTOTALLEN(len);
 735         result = (VarBit *) palloc(rlen);
 736         SET_VARSIZE(result, rlen);
 737         VARBITLEN(result) = len;
 738
 739         memcpy(VARBITS(result), VARBITS(arg), VARBITBYTES(result));
 740
 741         /* Make sure last byte is zero-padded if needed */
 742         ipad = VARBITPAD(result);
 743         if (ipad > 0)
 744         {
 745                 mask = BITMASK << ipad;
 746                 *(VARBITS(result) + VARBITBYTES(result) - 1) &= mask;
 747         }
 748
 749         PG_RETURN_VARBIT_P(result);
 750 }
 751
 752 Datum
 753 varbittypmodin(PG_FUNCTION_ARGS)
 754 {
 755         ArrayType  *ta = PG_GETARG_ARRAYTYPE_P(0);
 756
 757         PG_RETURN_INT32(anybit_typmodin(ta, "varbit"));
 758 }
 759
 760 Datum
 761 varbittypmodout(PG_FUNCTION_ARGS)
 762 {
 763         int32           typmod = PG_GETARG_INT32(0);
 764
 765         PG_RETURN_CSTRING(anybit_typmodout(typmod));
 766 }
 767
 768
 769 /*
 770  * Comparison operators
 771  *
 772  * We only need one set of comparison operators for bitstrings, as the lengths
 773  * are stored in the same way for zero-padded and varying bit strings.
 774  *
 775  * Note that the standard is not unambiguous about the comparison between
 776  * zero-padded bit strings and varying bitstrings. If the same value is written
 777  * into a zero padded bitstring as into a varying bitstring, but the zero
 778  * padded bitstring has greater length, it will be bigger.
 779  *
 780  * Zeros from the beginning of a bitstring cannot simply be ignored, as they
 781  * may be part of a bit string and may be significant.
 782  *
 783  * Note: btree indexes need these routines not to leak memory; therefore,
 784  * be careful to free working copies of toasted datums.  Most places don't
 785  * need to be so careful.
 786  */
 787
 788 /*
 789  * bit_cmp
 790  *
 791  * Compares two bitstrings and returns <0, 0, >0 depending on whether the first
 792  * string is smaller, equal, or bigger than the second. All bits are considered
 793  * and additional zero bits may make one string smaller/larger than the other,
 794  * even if their zero-padded values would be the same.
 795  */
 796 static int32
 797 bit_cmp(VarBit *arg1, VarBit *arg2)
 798 {
 799         int                     bitlen1,
 800                                 bytelen1,
 801                                 bitlen2,
 802                                 bytelen2;
 803         int32           cmp;
 804
 805         bytelen1 = VARBITBYTES(arg1);
 806         bytelen2 = VARBITBYTES(arg2);
 807
 808         cmp = memcmp(VARBITS(arg1), VARBITS(arg2), Min(bytelen1, bytelen2));
 809         if (cmp == 0)
 810         {
 811                 bitlen1 = VARBITLEN(arg1);
 812                 bitlen2 = VARBITLEN(arg2);
 813                 if (bitlen1 != bitlen2)
 814                         cmp = (bitlen1 < bitlen2) ? -1 : 1;
 815         }
 816         return cmp;
 817 }
 818
 819 Datum
 820 biteq(PG_FUNCTION_ARGS)
 821 {
 822         VarBit     *arg1 = PG_GETARG_VARBIT_P(0);
 823         VarBit     *arg2 = PG_GETARG_VARBIT_P(1);
 824         bool            result;
 825         int                     bitlen1,
 826                                 bitlen2;
 827
 828         bitlen1 = VARBITLEN(arg1);
 829         bitlen2 = VARBITLEN(arg2);
 830
 831         /* fast path for different-length inputs */
 832         if (bitlen1 != bitlen2)
 833                 result = false;
 834         else
 835                 result = (bit_cmp(arg1, arg2) == 0);
 836
 837         PG_FREE_IF_COPY(arg1, 0);
 838         PG_FREE_IF_COPY(arg2, 1);
 839
 840         PG_RETURN_BOOL(result);
 841 }
 842
 843 Datum
 844 bitne(PG_FUNCTION_ARGS)
 845 {
 846         VarBit     *arg1 = PG_GETARG_VARBIT_P(0);
 847         VarBit     *arg2 = PG_GETARG_VARBIT_P(1);
 848         bool            result;
 849         int                     bitlen1,
 850                                 bitlen2;
 851
 852         bitlen1 = VARBITLEN(arg1);
 853         bitlen2 = VARBITLEN(arg2);
 854
 855         /* fast path for different-length inputs */
 856         if (bitlen1 != bitlen2)
 857                 result = true;
 858         else
 859                 result = (bit_cmp(arg1, arg2) != 0);
 860
 861         PG_FREE_IF_COPY(arg1, 0);
 862         PG_FREE_IF_COPY(arg2, 1);
 863
 864         PG_RETURN_BOOL(result);
 865 }
 866
 867 Datum
 868 bitlt(PG_FUNCTION_ARGS)
 869 {
 870         VarBit     *arg1 = PG_GETARG_VARBIT_P(0);
 871         VarBit     *arg2 = PG_GETARG_VARBIT_P(1);
 872         bool            result;
 873
 874         result = (bit_cmp(arg1, arg2) < 0);
 875
 876         PG_FREE_IF_COPY(arg1, 0);
 877         PG_FREE_IF_COPY(arg2, 1);
 878
 879         PG_RETURN_BOOL(result);
 880 }
 881
 882 Datum
 883 bitle(PG_FUNCTION_ARGS)
 884 {
 885         VarBit     *arg1 = PG_GETARG_VARBIT_P(0);
 886         VarBit     *arg2 = PG_GETARG_VARBIT_P(1);
 887         bool            result;
 888
 889         result = (bit_cmp(arg1, arg2) <= 0);
 890
 891         PG_FREE_IF_COPY(arg1, 0);
 892         PG_FREE_IF_COPY(arg2, 1);
 893
 894         PG_RETURN_BOOL(result);
 895 }
 896
 897 Datum
 898 bitgt(PG_FUNCTION_ARGS)
 899 {
 900         VarBit     *arg1 = PG_GETARG_VARBIT_P(0);
 901         VarBit     *arg2 = PG_GETARG_VARBIT_P(1);
 902         bool            result;
 903
 904         result = (bit_cmp(arg1, arg2) > 0);
 905
 906         PG_FREE_IF_COPY(arg1, 0);
 907         PG_FREE_IF_COPY(arg2, 1);
 908
 909         PG_RETURN_BOOL(result);
 910 }
 911
 912 Datum
 913 bitge(PG_FUNCTION_ARGS)
 914 {
 915         VarBit     *arg1 = PG_GETARG_VARBIT_P(0);
 916         VarBit     *arg2 = PG_GETARG_VARBIT_P(1);
 917         bool            result;
 918
 919         result = (bit_cmp(arg1, arg2) >= 0);
 920
 921         PG_FREE_IF_COPY(arg1, 0);
 922         PG_FREE_IF_COPY(arg2, 1);
 923
 924         PG_RETURN_BOOL(result);
 925 }
 926
 927 Datum
 928 bitcmp(PG_FUNCTION_ARGS)
 929 {
 930         VarBit     *arg1 = PG_GETARG_VARBIT_P(0);
 931         VarBit     *arg2 = PG_GETARG_VARBIT_P(1);
 932         int32           result;
 933
 934         result = bit_cmp(arg1, arg2);
 935
 936         PG_FREE_IF_COPY(arg1, 0);
 937         PG_FREE_IF_COPY(arg2, 1);
 938
 939         PG_RETURN_INT32(result);
 940 }
 941
 942 /*
 943  * bitcat
 944  * Concatenation of bit strings
 945  */
 946 Datum
 947 bitcat(PG_FUNCTION_ARGS)
 948 {
 949         VarBit     *arg1 = PG_GETARG_VARBIT_P(0);
 950         VarBit     *arg2 = PG_GETARG_VARBIT_P(1);
 951
 952         PG_RETURN_VARBIT_P(bit_catenate(arg1, arg2));
 953 }
 954
 955 static VarBit *
 956 bit_catenate(VarBit *arg1, VarBit *arg2)
 957 {
 958         VarBit     *result;
 959         int                     bitlen1,
 960                                 bitlen2,
 961                                 bytelen,
 962                                 bit1pad,
 963                                 bit2shift;
 964         bits8      *pr,
 965                            *pa;
 966
 967         bitlen1 = VARBITLEN(arg1);
 968         bitlen2 = VARBITLEN(arg2);
 969
 970         if (bitlen1 > VARBITMAXLEN - bitlen2)
 971                 ereport(ERROR,
 972                                 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
 973                                  errmsg("bit string length exceeds the maximum allowed (%d)",
 974                                                 VARBITMAXLEN)));
 975         bytelen = VARBITTOTALLEN(bitlen1 + bitlen2);
 976
 977         result = (VarBit *) palloc(bytelen);
 978         SET_VARSIZE(result, bytelen);
 979         VARBITLEN(result) = bitlen1 + bitlen2;
 980
 981         /* Copy the first bitstring in */
 982         memcpy(VARBITS(result), VARBITS(arg1), VARBITBYTES(arg1));
 983
 984         /* Copy the second bit string */
 985         bit1pad = VARBITPAD(arg1);
 986         if (bit1pad == 0)
 987         {
 988                 memcpy(VARBITS(result) + VARBITBYTES(arg1), VARBITS(arg2),
 989                            VARBITBYTES(arg2));
 990         }
 991         else if (bitlen2 > 0)
 992         {
 993                 /* We need to shift all the bits to fit */
 994                 bit2shift = BITS_PER_BYTE - bit1pad;
 995                 pr = VARBITS(result) + VARBITBYTES(arg1) - 1;
 996                 for (pa = VARBITS(arg2); pa < VARBITEND(arg2); pa++)
 997                 {
 998                         *pr |= ((*pa >> bit2shift) & BITMASK);
 999                         pr++;
1000                         if (pr < VARBITEND(result))
1001                                 *pr = (*pa << bit1pad) & BITMASK;
1002                 }
1003         }
1004
1005         return result;
1006 }
1007
1008 /*
1009  * bitsubstr
1010  * retrieve a substring from the bit string.
1011  * Note, s is 1-based.
1012  * SQL draft 6.10 9)
1013  */
1014 Datum
1015 bitsubstr(PG_FUNCTION_ARGS)
1016 {
1017         PG_RETURN_VARBIT_P(bitsubstring(PG_GETARG_VARBIT_P(0),
1018                                                                         PG_GETARG_INT32(1),
1019                                                                         PG_GETARG_INT32(2),
1020                                                                         false));
1021 }
1022
1023 Datum
1024 bitsubstr_no_len(PG_FUNCTION_ARGS)
1025 {
1026         PG_RETURN_VARBIT_P(bitsubstring(PG_GETARG_VARBIT_P(0),
1027                                                                         PG_GETARG_INT32(1),
1028                                                                         -1, true));
1029 }
1030
1031 static VarBit *
1032 bitsubstring(VarBit *arg, int32 s, int32 l, bool length_not_specified)
1033 {
1034         VarBit     *result;
1035         int                     bitlen,
1036                                 rbitlen,
1037                                 len,
1038                                 ipad = 0,
1039                                 ishift,
1040                                 i;
1041         int                     e,
1042                                 s1,
1043                                 e1;
1044         bits8           mask,
1045                            *r,
1046                            *ps;
1047
1048         bitlen = VARBITLEN(arg);
1049         s1 = Max(s, 1);
1050         /* If we do not have an upper bound, use end of string */
1051         if (length_not_specified)
1052         {
1053                 e1 = bitlen + 1;
1054         }
1055         else
1056         {
1057                 e = s + l;
1058
1059                 /*
1060                  * A negative value for L is the only way for the end position to be
1061                  * before the start. SQL99 says to throw an error.
1062                  */
1063                 if (e < s)
1064                         ereport(ERROR,
1065                                         (errcode(ERRCODE_SUBSTRING_ERROR),
1066                                          errmsg("negative substring length not allowed")));
1067                 e1 = Min(e, bitlen + 1);
1068         }
1069         if (s1 > bitlen || e1 <= s1)
1070         {
1071                 /* Need to return a zero-length bitstring */
1072                 len = VARBITTOTALLEN(0);
1073                 result = (VarBit *) palloc(len);
1074                 SET_VARSIZE(result, len);
1075                 VARBITLEN(result) = 0;
1076         }
1077         else
1078         {
1079                 /*
1080                  * OK, we've got a true substring starting at position s1-1 and ending
1081                  * at position e1-1
1082                  */
1083                 rbitlen = e1 - s1;
1084                 len = VARBITTOTALLEN(rbitlen);
1085                 result = (VarBit *) palloc(len);
1086                 SET_VARSIZE(result, len);
1087                 VARBITLEN(result) = rbitlen;
1088                 len -= VARHDRSZ + VARBITHDRSZ;
1089                 /* Are we copying from a byte boundary? */
1090                 if ((s1 - 1) % BITS_PER_BYTE == 0)
1091                 {
1092                         /* Yep, we are copying bytes */
1093                         memcpy(VARBITS(result), VARBITS(arg) + (s1 - 1) / BITS_PER_BYTE,
1094                                    len);
1095                 }
1096                 else
1097                 {
1098                         /* Figure out how much we need to shift the sequence by */
1099                         ishift = (s1 - 1) % BITS_PER_BYTE;
1100                         r = VARBITS(result);
1101                         ps = VARBITS(arg) + (s1 - 1) / BITS_PER_BYTE;
1102                         for (i = 0; i < len; i++)
1103                         {
1104                                 *r = (*ps << ishift) & BITMASK;
1105                                 if ((++ps) < VARBITEND(arg))
1106                                         *r |= *ps >> (BITS_PER_BYTE - ishift);
1107                                 r++;
1108                         }
1109                 }
1110                 /* Do we need to pad at the end? */
1111                 ipad = VARBITPAD(result);
1112                 if (ipad > 0)
1113                 {
1114                         mask = BITMASK << ipad;
1115                         *(VARBITS(result) + len - 1) &= mask;
1116                 }
1117         }
1118
1119         return result;
1120 }
1121
1122 /*
1123  * bitoverlay
1124  *      Replace specified substring of first string with second
1125  *
1126  * The SQL standard defines OVERLAY() in terms of substring and concatenation.
1127  * This code is a direct implementation of what the standard says.
1128  */
1129 Datum
1130 bitoverlay(PG_FUNCTION_ARGS)
1131 {
1132         VarBit     *t1 = PG_GETARG_VARBIT_P(0);
1133         VarBit     *t2 = PG_GETARG_VARBIT_P(1);
1134         int                     sp = PG_GETARG_INT32(2);                /* substring start position */
1135         int                     sl = PG_GETARG_INT32(3);                /* substring length */
1136
1137         PG_RETURN_VARBIT_P(bit_overlay(t1, t2, sp, sl));
1138 }
1139
1140 Datum
1141 bitoverlay_no_len(PG_FUNCTION_ARGS)
1142 {
1143         VarBit     *t1 = PG_GETARG_VARBIT_P(0);
1144         VarBit     *t2 = PG_GETARG_VARBIT_P(1);
1145         int                     sp = PG_GETARG_INT32(2);                /* substring start position */
1146         int                     sl;
1147
1148         sl = VARBITLEN(t2);                     /* defaults to length(t2) */
1149         PG_RETURN_VARBIT_P(bit_overlay(t1, t2, sp, sl));
1150 }
1151
1152 static VarBit *
1153 bit_overlay(VarBit *t1, VarBit *t2, int sp, int sl)
1154 {
1155         VarBit     *result;
1156         VarBit     *s1;
1157         VarBit     *s2;
1158         int                     sp_pl_sl;
1159
1160         /*
1161          * Check for possible integer-overflow cases.  For negative sp, throw a
1162          * "substring length" error because that's what should be expected
1163          * according to the spec's definition of OVERLAY().
1164          */
1165         if (sp <= 0)
1166                 ereport(ERROR,
1167                                 (errcode(ERRCODE_SUBSTRING_ERROR),
1168                                  errmsg("negative substring length not allowed")));
1169         sp_pl_sl = sp + sl;
1170         if (sp_pl_sl <= sl)
1171                 ereport(ERROR,
1172                                 (errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),
1173                                  errmsg("integer out of range")));
1174
1175         s1 = bitsubstring(t1, 1, sp - 1, false);
1176         s2 = bitsubstring(t1, sp_pl_sl, -1, true);
1177         result = bit_catenate(s1, t2);
1178         result = bit_catenate(result, s2);
1179
1180         return result;
1181 }
1182
1183 /*
1184  * bitlength, bitoctetlength
1185  * Return the length of a bit string
1186  */
1187 Datum
1188 bitlength(PG_FUNCTION_ARGS)
1189 {
1190         VarBit     *arg = PG_GETARG_VARBIT_P(0);
1191
1192         PG_RETURN_INT32(VARBITLEN(arg));
1193 }
1194
1195 Datum
1196 bitoctetlength(PG_FUNCTION_ARGS)
1197 {
1198         VarBit     *arg = PG_GETARG_VARBIT_P(0);
1199
1200         PG_RETURN_INT32(VARBITBYTES(arg));
1201 }
1202
1203 /*
1204  * bit_and
1205  * perform a logical AND on two bit strings.
1206  */
1207 Datum
1208 bit_and(PG_FUNCTION_ARGS)
1209 {
1210         VarBit     *arg1 = PG_GETARG_VARBIT_P(0);
1211         VarBit     *arg2 = PG_GETARG_VARBIT_P(1);
1212         VarBit     *result;
1213         int                     len,
1214                                 bitlen1,
1215                                 bitlen2,
1216                                 i;
1217         bits8      *p1,
1218                            *p2,
1219                            *r;
1220
1221         bitlen1 = VARBITLEN(arg1);
1222         bitlen2 = VARBITLEN(arg2);
1223         if (bitlen1 != bitlen2)
1224                 ereport(ERROR,
1225                                 (errcode(ERRCODE_STRING_DATA_LENGTH_MISMATCH),
1226                                  errmsg("cannot AND bit strings of different sizes")));
1227
1228         len = VARSIZE(arg1);
1229         result = (VarBit *) palloc(len);
1230         SET_VARSIZE(result, len);
1231         VARBITLEN(result) = bitlen1;
1232
1233         p1 = VARBITS(arg1);
1234         p2 = VARBITS(arg2);
1235         r = VARBITS(result);
1236         for (i = 0; i < VARBITBYTES(arg1); i++)
1237                 *r++ = *p1++ & *p2++;
1238
1239         /* Padding is not needed as & of 0 pad is 0 */
1240
1241         PG_RETURN_VARBIT_P(result);
1242 }
1243
1244 /*
1245  * bit_or
1246  * perform a logical OR on two bit strings.
1247  */
1248 Datum
1249 bit_or(PG_FUNCTION_ARGS)
1250 {
1251         VarBit     *arg1 = PG_GETARG_VARBIT_P(0);
1252         VarBit     *arg2 = PG_GETARG_VARBIT_P(1);
1253         VarBit     *result;
1254         int                     len,
1255                                 bitlen1,
1256                                 bitlen2,
1257                                 i;
1258         bits8      *p1,
1259                            *p2,
1260                            *r;
1261         bits8           mask;
1262
1263         bitlen1 = VARBITLEN(arg1);
1264         bitlen2 = VARBITLEN(arg2);
1265         if (bitlen1 != bitlen2)
1266                 ereport(ERROR,
1267                                 (errcode(ERRCODE_STRING_DATA_LENGTH_MISMATCH),
1268                                  errmsg("cannot OR bit strings of different sizes")));
1269         len = VARSIZE(arg1);
1270         result = (VarBit *) palloc(len);
1271         SET_VARSIZE(result, len);
1272         VARBITLEN(result) = bitlen1;
1273
1274         p1 = VARBITS(arg1);
1275         p2 = VARBITS(arg2);
1276         r = VARBITS(result);
1277         for (i = 0; i < VARBITBYTES(arg1); i++)
1278                 *r++ = *p1++ | *p2++;
1279
1280         /* Pad the result */
1281         mask = BITMASK << VARBITPAD(result);
1282         if (mask)
1283         {
1284                 r--;
1285                 *r &= mask;
1286         }
1287
1288         PG_RETURN_VARBIT_P(result);
1289 }
1290
1291 /*
1292  * bitxor
1293  * perform a logical XOR on two bit strings.
1294  */
1295 Datum
1296 bitxor(PG_FUNCTION_ARGS)
1297 {
1298         VarBit     *arg1 = PG_GETARG_VARBIT_P(0);
1299         VarBit     *arg2 = PG_GETARG_VARBIT_P(1);
1300         VarBit     *result;
1301         int                     len,
1302                                 bitlen1,
1303                                 bitlen2,
1304                                 i;
1305         bits8      *p1,
1306                            *p2,
1307                            *r;
1308         bits8           mask;
1309
1310         bitlen1 = VARBITLEN(arg1);
1311         bitlen2 = VARBITLEN(arg2);
1312         if (bitlen1 != bitlen2)
1313                 ereport(ERROR,
1314                                 (errcode(ERRCODE_STRING_DATA_LENGTH_MISMATCH),
1315                                  errmsg("cannot XOR bit strings of different sizes")));
1316
1317         len = VARSIZE(arg1);
1318         result = (VarBit *) palloc(len);
1319         SET_VARSIZE(result, len);
1320         VARBITLEN(result) = bitlen1;
1321
1322         p1 = VARBITS(arg1);
1323         p2 = VARBITS(arg2);
1324         r = VARBITS(result);
1325         for (i = 0; i < VARBITBYTES(arg1); i++)
1326                 *r++ = *p1++ ^ *p2++;
1327
1328         /* Pad the result */
1329         mask = BITMASK << VARBITPAD(result);
1330         if (mask)
1331         {
1332                 r--;
1333                 *r &= mask;
1334         }
1335
1336         PG_RETURN_VARBIT_P(result);
1337 }
1338
1339 /*
1340  * bitnot
1341  * perform a logical NOT on a bit string.
1342  */
1343 Datum
1344 bitnot(PG_FUNCTION_ARGS)
1345 {
1346         VarBit     *arg = PG_GETARG_VARBIT_P(0);
1347         VarBit     *result;
1348         bits8      *p,
1349                            *r;
1350         bits8           mask;
1351
1352         result = (VarBit *) palloc(VARSIZE(arg));
1353         SET_VARSIZE(result, VARSIZE(arg));
1354         VARBITLEN(result) = VARBITLEN(arg);
1355
1356         p = VARBITS(arg);
1357         r = VARBITS(result);
1358         for (; p < VARBITEND(arg); p++)
1359                 *r++ = ~*p;
1360
1361         /* Pad the result */
1362         mask = BITMASK << VARBITPAD(result);
1363         if (mask)
1364         {
1365                 r--;
1366                 *r &= mask;
1367         }
1368
1369         PG_RETURN_VARBIT_P(result);
1370 }
1371
1372 /*
1373  * bitshiftleft
1374  * do a left shift (i.e. towards the beginning of the string)
1375  */
1376 Datum
1377 bitshiftleft(PG_FUNCTION_ARGS)
1378 {
1379         VarBit     *arg = PG_GETARG_VARBIT_P(0);
1380         int32           shft = PG_GETARG_INT32(1);
1381         VarBit     *result;
1382         int                     byte_shift,
1383                                 ishift,
1384                                 len;
1385         bits8      *p,
1386                            *r;
1387
1388         /* Negative shift is a shift to the right */
1389         if (shft < 0)
1390         {
1391                 /* Prevent integer overflow in negation */
1392                 if (shft < -VARBITMAXLEN)
1393                         shft = -VARBITMAXLEN;
1394                 PG_RETURN_DATUM(DirectFunctionCall2(bitshiftright,
1395                                                                                         VarBitPGetDatum(arg),
1396                                                                                         Int32GetDatum(-shft)));
1397         }
1398
1399         result = (VarBit *) palloc(VARSIZE(arg));
1400         SET_VARSIZE(result, VARSIZE(arg));
1401         VARBITLEN(result) = VARBITLEN(arg);
1402         r = VARBITS(result);
1403
1404         /* If we shifted all the bits out, return an all-zero string */
1405         if (shft >= VARBITLEN(arg))
1406         {
1407                 MemSet(r, 0, VARBITBYTES(arg));
1408                 PG_RETURN_VARBIT_P(result);
1409         }
1410
1411         byte_shift = shft / BITS_PER_BYTE;
1412         ishift = shft % BITS_PER_BYTE;
1413         p = VARBITS(arg) + byte_shift;
1414
1415         if (ishift == 0)
1416         {
1417                 /* Special case: we can do a memcpy */
1418                 len = VARBITBYTES(arg) - byte_shift;
1419                 memcpy(r, p, len);
1420                 MemSet(r + len, 0, byte_shift);
1421         }
1422         else
1423         {
1424                 for (; p < VARBITEND(arg); r++)
1425                 {
1426                         *r = *p << ishift;
1427                         if ((++p) < VARBITEND(arg))
1428                                 *r |= *p >> (BITS_PER_BYTE - ishift);
1429                 }
1430                 for (; r < VARBITEND(result); r++)
1431                         *r = 0;
1432         }
1433
1434         PG_RETURN_VARBIT_P(result);
1435 }
1436
1437 /*
1438  * bitshiftright
1439  * do a right shift (i.e. towards the end of the string)
1440  */
1441 Datum
1442 bitshiftright(PG_FUNCTION_ARGS)
1443 {
1444         VarBit     *arg = PG_GETARG_VARBIT_P(0);
1445         int32           shft = PG_GETARG_INT32(1);
1446         VarBit     *result;
1447         int                     byte_shift,
1448                                 ishift,
1449                                 len;
1450         bits8      *p,
1451                            *r;
1452
1453         /* Negative shift is a shift to the left */
1454         if (shft < 0)
1455         {
1456                 /* Prevent integer overflow in negation */
1457                 if (shft < -VARBITMAXLEN)
1458                         shft = -VARBITMAXLEN;
1459                 PG_RETURN_DATUM(DirectFunctionCall2(bitshiftleft,
1460                                                                                         VarBitPGetDatum(arg),
1461                                                                                         Int32GetDatum(-shft)));
1462         }
1463
1464         result = (VarBit *) palloc(VARSIZE(arg));
1465         SET_VARSIZE(result, VARSIZE(arg));
1466         VARBITLEN(result) = VARBITLEN(arg);
1467         r = VARBITS(result);
1468
1469         /* If we shifted all the bits out, return an all-zero string */
1470         if (shft >= VARBITLEN(arg))
1471         {
1472                 MemSet(r, 0, VARBITBYTES(arg));
1473                 PG_RETURN_VARBIT_P(result);
1474         }
1475
1476         byte_shift = shft / BITS_PER_BYTE;
1477         ishift = shft % BITS_PER_BYTE;
1478         p = VARBITS(arg);
1479
1480         /* Set the first part of the result to 0 */
1481         MemSet(r, 0, byte_shift);
1482         r += byte_shift;
1483
1484         if (ishift == 0)
1485         {
1486                 /* Special case: we can do a memcpy */
1487                 len = VARBITBYTES(arg) - byte_shift;
1488                 memcpy(r, p, len);
1489         }
1490         else
1491         {
1492                 if (r < VARBITEND(result))
1493                         *r = 0;                         /* initialize first byte */
1494                 for (; r < VARBITEND(result); p++)
1495                 {
1496                         *r |= *p >> ishift;
1497                         if ((++r) < VARBITEND(result))
1498                                 *r = (*p << (BITS_PER_BYTE - ishift)) & BITMASK;
1499                 }
1500         }
1501
1502         PG_RETURN_VARBIT_P(result);
1503 }
1504
1505 /*
1506  * This is not defined in any standard. We retain the natural ordering of
1507  * bits here, as it just seems more intuitive.
1508  */
1509 Datum
1510 bitfromint4(PG_FUNCTION_ARGS)
1511 {
1512         int32           a = PG_GETARG_INT32(0);
1513         int32           typmod = PG_GETARG_INT32(1);
1514         VarBit     *result;
1515         bits8      *r;
1516         int                     rlen;
1517         int                     destbitsleft,
1518                                 srcbitsleft;
1519
1520         if (typmod <= 0 || typmod > VARBITMAXLEN)
1521                 typmod = 1;                             /* default bit length */
1522
1523         rlen = VARBITTOTALLEN(typmod);
1524         result = (VarBit *) palloc(rlen);
1525         SET_VARSIZE(result, rlen);
1526         VARBITLEN(result) = typmod;
1527
1528         r = VARBITS(result);
1529         destbitsleft = typmod;
1530         srcbitsleft = 32;
1531         /* drop any input bits that don't fit */
1532         srcbitsleft = Min(srcbitsleft, destbitsleft);
1533         /* sign-fill any excess bytes in output */
1534         while (destbitsleft >= srcbitsleft + 8)
1535         {
1536                 *r++ = (bits8) ((a < 0) ? BITMASK : 0);
1537                 destbitsleft -= 8;
1538         }
1539         /* store first fractional byte */
1540         if (destbitsleft > srcbitsleft)
1541         {
1542                 int                     val = (int) (a >> (destbitsleft - 8));
1543
1544                 /* Force sign-fill in case the compiler implements >> as zero-fill */
1545                 if (a < 0)
1546                         val |= (-1) << (srcbitsleft + 8 - destbitsleft);
1547                 *r++ = (bits8) (val & BITMASK);
1548                 destbitsleft -= 8;
1549         }
1550         /* Now srcbitsleft and destbitsleft are the same, need not track both */
1551         /* store whole bytes */
1552         while (destbitsleft >= 8)
1553         {
1554                 *r++ = (bits8) ((a >> (destbitsleft - 8)) & BITMASK);
1555                 destbitsleft -= 8;
1556         }
1557         /* store last fractional byte */
1558         if (destbitsleft > 0)
1559                 *r = (bits8) ((a << (8 - destbitsleft)) & BITMASK);
1560
1561         PG_RETURN_VARBIT_P(result);
1562 }
1563
1564 Datum
1565 bittoint4(PG_FUNCTION_ARGS)
1566 {
1567         VarBit     *arg = PG_GETARG_VARBIT_P(0);
1568         uint32          result;
1569         bits8      *r;
1570
1571         /* Check that the bit string is not too long */
1572         if (VARBITLEN(arg) > sizeof(result) * BITS_PER_BYTE)
1573                 ereport(ERROR,
1574                                 (errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),
1575                                  errmsg("integer out of range")));
1576
1577         result = 0;
1578         for (r = VARBITS(arg); r < VARBITEND(arg); r++)
1579         {
1580                 result <<= BITS_PER_BYTE;
1581                 result |= *r;
1582         }
1583         /* Now shift the result to take account of the padding at the end */
1584         result >>= VARBITPAD(arg);
1585
1586         PG_RETURN_INT32(result);
1587 }
1588
1589 Datum
1590 bitfromint8(PG_FUNCTION_ARGS)
1591 {
1592         int64           a = PG_GETARG_INT64(0);
1593         int32           typmod = PG_GETARG_INT32(1);
1594         VarBit     *result;
1595         bits8      *r;
1596         int                     rlen;
1597         int                     destbitsleft,
1598                                 srcbitsleft;
1599
1600         if (typmod <= 0 || typmod > VARBITMAXLEN)
1601                 typmod = 1;                             /* default bit length */
1602
1603         rlen = VARBITTOTALLEN(typmod);
1604         result = (VarBit *) palloc(rlen);
1605         SET_VARSIZE(result, rlen);
1606         VARBITLEN(result) = typmod;
1607
1608         r = VARBITS(result);
1609         destbitsleft = typmod;
1610         srcbitsleft = 64;
1611         /* drop any input bits that don't fit */
1612         srcbitsleft = Min(srcbitsleft, destbitsleft);
1613         /* sign-fill any excess bytes in output */
1614         while (destbitsleft >= srcbitsleft + 8)
1615         {
1616                 *r++ = (bits8) ((a < 0) ? BITMASK : 0);
1617                 destbitsleft -= 8;
1618         }
1619         /* store first fractional byte */
1620         if (destbitsleft > srcbitsleft)
1621         {
1622                 int                     val = (int) (a >> (destbitsleft - 8));
1623
1624                 /* Force sign-fill in case the compiler implements >> as zero-fill */
1625                 if (a < 0)
1626                         val |= (-1) << (srcbitsleft + 8 - destbitsleft);
1627                 *r++ = (bits8) (val & BITMASK);
1628                 destbitsleft -= 8;
1629         }
1630         /* Now srcbitsleft and destbitsleft are the same, need not track both */
1631         /* store whole bytes */
1632         while (destbitsleft >= 8)
1633         {
1634                 *r++ = (bits8) ((a >> (destbitsleft - 8)) & BITMASK);
1635                 destbitsleft -= 8;
1636         }
1637         /* store last fractional byte */
1638         if (destbitsleft > 0)
1639                 *r = (bits8) ((a << (8 - destbitsleft)) & BITMASK);
1640
1641         PG_RETURN_VARBIT_P(result);
1642 }
1643
1644 Datum
1645 bittoint8(PG_FUNCTION_ARGS)
1646 {
1647         VarBit     *arg = PG_GETARG_VARBIT_P(0);
1648         uint64          result;
1649         bits8      *r;
1650
1651         /* Check that the bit string is not too long */
1652         if (VARBITLEN(arg) > sizeof(result) * BITS_PER_BYTE)
1653                 ereport(ERROR,
1654                                 (errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),
1655                                  errmsg("bigint out of range")));
1656
1657         result = 0;
1658         for (r = VARBITS(arg); r < VARBITEND(arg); r++)
1659         {
1660                 result <<= BITS_PER_BYTE;
1661                 result |= *r;
1662         }
1663         /* Now shift the result to take account of the padding at the end */
1664         result >>= VARBITPAD(arg);
1665
1666         PG_RETURN_INT64(result);
1667 }
1668
1669
1670 /*
1671  * Determines the position of S2 in the bitstring S1 (1-based string).
1672  * If S2 does not appear in S1 this function returns 0.
1673  * If S2 is of length 0 this function returns 1.
1674  * Compatible in usage with POSITION() functions for other data types.
1675  */
1676 Datum
1677 bitposition(PG_FUNCTION_ARGS)
1678 {
1679         VarBit     *str = PG_GETARG_VARBIT_P(0);
1680         VarBit     *substr = PG_GETARG_VARBIT_P(1);
1681         int                     substr_length,
1682                                 str_length,
1683                                 i,
1684                                 is;
1685         bits8      *s,                          /* pointer into substring */
1686                            *p;                          /* pointer into str */
1687         bits8           cmp,                    /* shifted substring byte to compare */
1688                                 mask1,                  /* mask for substring byte shifted right */
1689                                 mask2,                  /* mask for substring byte shifted left */
1690                                 end_mask,               /* pad mask for last substring byte */
1691                                 str_mask;               /* pad mask for last string byte */
1692         bool            is_match;
1693
1694         /* Get the substring length */
1695         substr_length = VARBITLEN(substr);
1696         str_length = VARBITLEN(str);
1697
1698         /* String has zero length or substring longer than string, return 0 */
1699         if ((str_length == 0) || (substr_length > str_length))
1700                 PG_RETURN_INT32(0);
1701
1702         /* zero-length substring means return 1 */
1703         if (substr_length == 0)
1704                 PG_RETURN_INT32(1);
1705
1706         /* Initialise the padding masks */
1707         end_mask = BITMASK << VARBITPAD(substr);
1708         str_mask = BITMASK << VARBITPAD(str);
1709         for (i = 0; i < VARBITBYTES(str) - VARBITBYTES(substr) + 1; i++)
1710         {
1711                 for (is = 0; is < BITS_PER_BYTE; is++)
1712                 {
1713                         is_match = true;
1714                         p = VARBITS(str) + i;
1715                         mask1 = BITMASK >> is;
1716                         mask2 = ~mask1;
1717                         for (s = VARBITS(substr);
1718                                  is_match && s < VARBITEND(substr); s++)
1719                         {
1720                                 cmp = *s >> is;
1721                                 if (s == VARBITEND(substr) - 1)
1722                                 {
1723                                         mask1 &= end_mask >> is;
1724                                         if (p == VARBITEND(str) - 1)
1725                                         {
1726                                                 /* Check that there is enough of str left */
1727                                                 if (mask1 & ~str_mask)
1728                                                 {
1729                                                         is_match = false;
1730                                                         break;
1731                                                 }
1732                                                 mask1 &= str_mask;
1733                                         }
1734                                 }
1735                                 is_match = ((cmp ^ *p) & mask1) == 0;
1736                                 if (!is_match)
1737                                         break;
1738                                 /* Move on to the next byte */
1739                                 p++;
1740                                 if (p == VARBITEND(str))
1741                                 {
1742                                         mask2 = end_mask << (BITS_PER_BYTE - is);
1743                                         is_match = mask2 == 0;
1744 #if 0
1745                                         elog(DEBUG4, "S. %d %d em=%2x sm=%2x r=%d",
1746                                                  i, is, end_mask, mask2, is_match);
1747 #endif
1748                                         break;
1749                                 }
1750                                 cmp = *s << (BITS_PER_BYTE - is);
1751                                 if (s == VARBITEND(substr) - 1)
1752                                 {
1753                                         mask2 &= end_mask << (BITS_PER_BYTE - is);
1754                                         if (p == VARBITEND(str) - 1)
1755                                         {
1756                                                 if (mask2 & ~str_mask)
1757                                                 {
1758                                                         is_match = false;
1759                                                         break;
1760                                                 }
1761                                                 mask2 &= str_mask;
1762                                         }
1763                                 }
1764                                 is_match = ((cmp ^ *p) & mask2) == 0;
1765                         }
1766                         /* Have we found a match? */
1767                         if (is_match)
1768                                 PG_RETURN_INT32(i * BITS_PER_BYTE + is + 1);
1769                 }
1770         }
1771         PG_RETURN_INT32(0);
1772 }
1773
1774
1775 /*
1776  * bitsetbit
1777  *
1778  * Given an instance of type 'bit' creates a new one with
1779  * the Nth bit set to the given value.
1780  *
1781  * The bit location is specified left-to-right in a zero-based fashion
1782  * consistent with the other get_bit and set_bit functions, but
1783  * inconsistent with the standard substring, position, overlay functions
1784  */
1785 Datum
1786 bitsetbit(PG_FUNCTION_ARGS)
1787 {
1788         VarBit     *arg1 = PG_GETARG_VARBIT_P(0);
1789         int32           n = PG_GETARG_INT32(1);
1790         int32           newBit = PG_GETARG_INT32(2);
1791         VarBit     *result;
1792         int                     len,
1793                                 bitlen;
1794         bits8      *r,
1795                            *p;
1796         int                     byteNo,
1797                                 bitNo;
1798
1799         bitlen = VARBITLEN(arg1);
1800         if (n < 0 || n >= bitlen)
1801                 ereport(ERROR,
1802                                 (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
1803                                  errmsg("bit index %d out of valid range (0..%d)",
1804                                                 n, bitlen - 1)));
1805
1806         /*
1807          * sanity check!
1808          */
1809         if (newBit != 0 && newBit != 1)
1810                 ereport(ERROR,
1811                                 (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
1812                                  errmsg("new bit must be 0 or 1")));
1813
1814         len = VARSIZE(arg1);
1815         result = (VarBit *) palloc(len);
1816         SET_VARSIZE(result, len);
1817         VARBITLEN(result) = bitlen;
1818
1819         p = VARBITS(arg1);
1820         r = VARBITS(result);
1821
1822         memcpy(r, p, VARBITBYTES(arg1));
1823
1824         byteNo = n / BITS_PER_BYTE;
1825         bitNo = BITS_PER_BYTE - 1 - (n % BITS_PER_BYTE);
1826
1827         /*
1828          * Update the byte.
1829          */
1830         if (newBit == 0)
1831                 r[byteNo] &= (~(1 << bitNo));
1832         else
1833                 r[byteNo] |= (1 << bitNo);
1834
1835         PG_RETURN_VARBIT_P(result);
1836 }
1837
1838 /*
1839  * bitgetbit
1840  *
1841  * returns the value of the Nth bit of a bit array (0 or 1).
1842  *
1843  * The bit location is specified left-to-right in a zero-based fashion
1844  * consistent with the other get_bit and set_bit functions, but
1845  * inconsistent with the standard substring, position, overlay functions
1846  */
1847 Datum
1848 bitgetbit(PG_FUNCTION_ARGS)
1849 {
1850         VarBit     *arg1 = PG_GETARG_VARBIT_P(0);
1851         int32           n = PG_GETARG_INT32(1);
1852         int                     bitlen;
1853         bits8      *p;
1854         int                     byteNo,
1855                                 bitNo;
1856
1857         bitlen = VARBITLEN(arg1);
1858         if (n < 0 || n >= bitlen)
1859                 ereport(ERROR,
1860                                 (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
1861                                  errmsg("bit index %d out of valid range (0..%d)",
1862                                                 n, bitlen - 1)));
1863
1864         p = VARBITS(arg1);
1865
1866         byteNo = n / BITS_PER_BYTE;
1867         bitNo = BITS_PER_BYTE - 1 - (n % BITS_PER_BYTE);
1868
1869         if (p[byteNo] & (1 << bitNo))
1870                 PG_RETURN_INT32(1);
1871         else
1872                 PG_RETURN_INT32(0);
1873 }