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