PostgreSQL Source Code  git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
pg_bitutils.c File Reference
#include "c.h"
#include "port/pg_bitutils.h"
Include dependency graph for pg_bitutils.c:

Go to the source code of this file.

Functions

static int pg_popcount32_slow (uint32 word)
 
static int pg_popcount64_slow (uint64 word)
 
static uint64 pg_popcount_slow (const char *buf, int bytes)
 
static uint64 pg_popcount_masked_slow (const char *buf, int bytes, bits8 mask)
 
int pg_popcount32 (uint32 word)
 
int pg_popcount64 (uint64 word)
 
uint64 pg_popcount_optimized (const char *buf, int bytes)
 
uint64 pg_popcount_masked_optimized (const char *buf, int bytes, bits8 mask)
 

Variables

const uint8 pg_leftmost_one_pos [256]
 
const uint8 pg_rightmost_one_pos [256]
 
const uint8 pg_number_of_ones [256]
 

Function Documentation

◆ pg_popcount32()

int pg_popcount32 ( uint32  word)

Definition at line 499 of file pg_bitutils.c.

500 {
501  return pg_popcount32_slow(word);
502 }
static int pg_popcount32_slow(uint32 word)
Definition: pg_bitutils.c:348
static void word(struct vars *v, int dir, struct state *lp, struct state *rp)
Definition: regcomp.c:1476

References pg_popcount32_slow(), and word().

Referenced by plan_single_revoke().

◆ pg_popcount32_slow()

static int pg_popcount32_slow ( uint32  word)
inlinestatic

Definition at line 348 of file pg_bitutils.c.

349 {
350 #ifdef HAVE__BUILTIN_POPCOUNT
351  return __builtin_popcount(word);
352 #else /* !HAVE__BUILTIN_POPCOUNT */
353  int result = 0;
354 
355  while (word != 0)
356  {
357  result += pg_number_of_ones[word & 255];
358  word >>= 8;
359  }
360 
361  return result;
362 #endif /* HAVE__BUILTIN_POPCOUNT */
363 }
const uint8 pg_number_of_ones[256]
Definition: pg_bitutils.c:87

References pg_number_of_ones, and word().

Referenced by pg_popcount32(), pg_popcount_masked_slow(), and pg_popcount_slow().

◆ pg_popcount64()

int pg_popcount64 ( uint64  word)

Definition at line 505 of file pg_bitutils.c.

506 {
507  return pg_popcount64_slow(word);
508 }
static int pg_popcount64_slow(uint64 word)
Definition: pg_bitutils.c:370

References pg_popcount64_slow(), and word().

◆ pg_popcount64_slow()

static int pg_popcount64_slow ( uint64  word)
inlinestatic

Definition at line 370 of file pg_bitutils.c.

371 {
372 #ifdef HAVE__BUILTIN_POPCOUNT
373 #if defined(HAVE_LONG_INT_64)
374  return __builtin_popcountl(word);
375 #elif defined(HAVE_LONG_LONG_INT_64)
376  return __builtin_popcountll(word);
377 #else
378 #error must have a working 64-bit integer datatype
379 #endif
380 #else /* !HAVE__BUILTIN_POPCOUNT */
381  int result = 0;
382 
383  while (word != 0)
384  {
385  result += pg_number_of_ones[word & 255];
386  word >>= 8;
387  }
388 
389  return result;
390 #endif /* HAVE__BUILTIN_POPCOUNT */
391 }

References pg_number_of_ones, and word().

Referenced by pg_popcount64(), pg_popcount_masked_slow(), and pg_popcount_slow().

◆ pg_popcount_masked_optimized()

uint64 pg_popcount_masked_optimized ( const char *  buf,
int  bytes,
bits8  mask 
)

Definition at line 525 of file pg_bitutils.c.

526 {
527  return pg_popcount_masked_slow(buf, bytes, mask);
528 }
static uint64 pg_popcount_masked_slow(const char *buf, int bytes, bits8 mask)
Definition: pg_bitutils.c:444
static char * buf
Definition: pg_test_fsync.c:72

References buf, and pg_popcount_masked_slow().

Referenced by pg_popcount_masked().

◆ pg_popcount_masked_slow()

static uint64 pg_popcount_masked_slow ( const char *  buf,
int  bytes,
bits8  mask 
)
static

Definition at line 444 of file pg_bitutils.c.

445 {
446  uint64 popcnt = 0;
447 
448 #if SIZEOF_VOID_P >= 8
449  /* Process in 64-bit chunks if the buffer is aligned */
450  uint64 maskv = ~UINT64CONST(0) / 0xFF * mask;
451 
452  if (buf == (const char *) TYPEALIGN(8, buf))
453  {
454  const uint64 *words = (const uint64 *) buf;
455 
456  while (bytes >= 8)
457  {
458  popcnt += pg_popcount64_slow(*words++ & maskv);
459  bytes -= 8;
460  }
461 
462  buf = (const char *) words;
463  }
464 #else
465  /* Process in 32-bit chunks if the buffer is aligned. */
466  uint32 maskv = ~((uint32) 0) / 0xFF * mask;
467 
468  if (buf == (const char *) TYPEALIGN(4, buf))
469  {
470  const uint32 *words = (const uint32 *) buf;
471 
472  while (bytes >= 4)
473  {
474  popcnt += pg_popcount32_slow(*words++ & maskv);
475  bytes -= 4;
476  }
477 
478  buf = (const char *) words;
479  }
480 #endif
481 
482  /* Process any remaining bytes */
483  while (bytes--)
484  popcnt += pg_number_of_ones[(unsigned char) *buf++ & mask];
485 
486  return popcnt;
487 }
unsigned int uint32
Definition: c.h:492
#define TYPEALIGN(ALIGNVAL, LEN)
Definition: c.h:783

References buf, pg_number_of_ones, pg_popcount32_slow(), pg_popcount64_slow(), and TYPEALIGN.

Referenced by pg_popcount_masked_optimized().

◆ pg_popcount_optimized()

uint64 pg_popcount_optimized ( const char *  buf,
int  bytes 
)

Definition at line 515 of file pg_bitutils.c.

516 {
517  return pg_popcount_slow(buf, bytes);
518 }
static uint64 pg_popcount_slow(const char *buf, int bytes)
Definition: pg_bitutils.c:398

References buf, and pg_popcount_slow().

Referenced by pg_popcount().

◆ pg_popcount_slow()

static uint64 pg_popcount_slow ( const char *  buf,
int  bytes 
)
static

Definition at line 398 of file pg_bitutils.c.

399 {
400  uint64 popcnt = 0;
401 
402 #if SIZEOF_VOID_P >= 8
403  /* Process in 64-bit chunks if the buffer is aligned. */
404  if (buf == (const char *) TYPEALIGN(8, buf))
405  {
406  const uint64 *words = (const uint64 *) buf;
407 
408  while (bytes >= 8)
409  {
410  popcnt += pg_popcount64_slow(*words++);
411  bytes -= 8;
412  }
413 
414  buf = (const char *) words;
415  }
416 #else
417  /* Process in 32-bit chunks if the buffer is aligned. */
418  if (buf == (const char *) TYPEALIGN(4, buf))
419  {
420  const uint32 *words = (const uint32 *) buf;
421 
422  while (bytes >= 4)
423  {
424  popcnt += pg_popcount32_slow(*words++);
425  bytes -= 4;
426  }
427 
428  buf = (const char *) words;
429  }
430 #endif
431 
432  /* Process any remaining bytes */
433  while (bytes--)
434  popcnt += pg_number_of_ones[(unsigned char) *buf++];
435 
436  return popcnt;
437 }

References buf, pg_number_of_ones, pg_popcount32_slow(), pg_popcount64_slow(), and TYPEALIGN.

Referenced by pg_popcount_optimized().

Variable Documentation

◆ pg_leftmost_one_pos

const uint8 pg_leftmost_one_pos[256]
Initial value:
= {
0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
}

Definition at line 34 of file pg_bitutils.c.

Referenced by AllocSetFreeIndex(), pg_leftmost_one_pos32(), and pg_leftmost_one_pos64().

◆ pg_number_of_ones

const uint8 pg_number_of_ones[256]
Initial value:
= {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
}

Definition at line 87 of file pg_bitutils.c.

Referenced by hemdistsign(), pg_popcount(), pg_popcount32_slow(), pg_popcount64_slow(), pg_popcount_masked(), pg_popcount_masked_slow(), pg_popcount_slow(), and process_pipe_input().

◆ pg_rightmost_one_pos

const uint8 pg_rightmost_one_pos[256]
Initial value:
= {
0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
}

Definition at line 62 of file pg_bitutils.c.

Referenced by pg_rightmost_one_pos32(), and pg_rightmost_one_pos64().