PostgreSQL Source Code git master
Functions | Variables
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 509 of file pg_bitutils.c.

510{
511 return pg_popcount32_slow(word);
512}
static int pg_popcount32_slow(uint32 word)
Definition: pg_bitutils.c:357
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 357 of file pg_bitutils.c.

358{
359#ifdef HAVE__BUILTIN_POPCOUNT
360 return __builtin_popcount(word);
361#else /* !HAVE__BUILTIN_POPCOUNT */
362 int result = 0;
363
364 while (word != 0)
365 {
366 result += pg_number_of_ones[word & 255];
367 word >>= 8;
368 }
369
370 return result;
371#endif /* HAVE__BUILTIN_POPCOUNT */
372}
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 515 of file pg_bitutils.c.

516{
517 return pg_popcount64_slow(word);
518}
static int pg_popcount64_slow(uint64 word)
Definition: pg_bitutils.c:379

References pg_popcount64_slow(), and word().

Referenced by select_best_grantor().

◆ pg_popcount64_slow()

static int pg_popcount64_slow ( uint64  word )
inlinestatic

Definition at line 379 of file pg_bitutils.c.

380{
381#ifdef HAVE__BUILTIN_POPCOUNT
382#if SIZEOF_LONG == 8
383 return __builtin_popcountl(word);
384#elif SIZEOF_LONG_LONG == 8
385 return __builtin_popcountll(word);
386#else
387#error "cannot find integer of the same size as uint64_t"
388#endif
389#else /* !HAVE__BUILTIN_POPCOUNT */
390 int result = 0;
391
392 while (word != 0)
393 {
394 result += pg_number_of_ones[word & 255];
395 word >>= 8;
396 }
397
398 return result;
399#endif /* HAVE__BUILTIN_POPCOUNT */
400}

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 535 of file pg_bitutils.c.

536{
537 return pg_popcount_masked_slow(buf, bytes, mask);
538}
static uint64 pg_popcount_masked_slow(const char *buf, int bytes, bits8 mask)
Definition: pg_bitutils.c:453
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 453 of file pg_bitutils.c.

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

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 525 of file pg_bitutils.c.

526{
527 return pg_popcount_slow(buf, bytes);
528}
static uint64 pg_popcount_slow(const char *buf, int bytes)
Definition: pg_bitutils.c:407

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 407 of file pg_bitutils.c.

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

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().

AltStyle によって変換されたページ (->オリジナル) /