Changeset 1550 for trunk


Ignore:
Timestamp:
Oct 22, 2011, 2:14:12 PM (8 years ago)
Author:
ksherdy
Message:

Add count_forward_zeroes, count_backward_zeroes.

Location:
trunk/lib
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • trunk/lib/bitblock.hpp

    r1542 r1550  
    1515#include "idisa.hpp"
    1616
     17#include <limits>
     18#ifndef LONG_BIT
     19#if ULONG_MAX == 0xFFFFFFFF
     20#define LONG_BIT 32
     21#endif
     22#if ULONG_MAX == 0xFFFFFFFFFFFFFFFF
     23#define LONG_BIT 64
     24#endif
     25#endif
     26
    1727#ifndef BLOCKSIZE
    1828#define BLOCKSIZE 128
     
    2131/*  Default BLOCKSIZE is 128, compatible with SSE, Altivec, SPU */
    2232#if (BLOCKSIZE == 128)
    23 #include "idisa128.hpp"
    2433#include "bitblock128.hpp"
    2534#endif
     
    2736/*  BLOCKSIZE 256 for AVX */
    2837#if (BLOCKSIZE == 256)
    29 #include "idisa256.hpp"
    3038#include "bitblock256.hpp"
    3139#endif
    3240
    3341/* Wrapper Declarations */
    34 
     42/*
    3543#define sisd_sll(blk, n) simd<128>::sll(blk, n)         // TODO - Deprecate 'sisd_f(x,y)'. bitblock_f(x,y) Migrate to simd<sizeof(BitBlock)*8>::f(x,y) or simd<bitblock128_t, 128>::f(x,y)
    3644#define sisd_srl(blk, n) simd<128>::srl(blk, n)
     
    4351#define sb_op(x, n) ((x)>>(n))
    4452#define sf_op(x, n) ((x)<<(n))
    45 
     53*/
    4654
    4755template<class T> void print_register(const char * var_name, T v);      // print integer types as array of unsigned char
  • trunk/lib/bitblock128.hpp

    r1542 r1550  
    11/*
    2     bitblock128 - 128 bit block size - Specific 128 bit implementations.
     2    bitblock128 - Specific 128 bit IDISA implementations.
    33
    44    Idealized SIMD Operations with SSE versions
     
    1212#define BITBLOCK128_HPP_
    1313
     14#include "idisa128.hpp"
     15
     16union ubitblock128 {
     17        bitblock128_t _128;
     18        uint64_t _64[sizeof(bitblock128_t)/sizeof(uint64_t)];
     19        uint32_t _32[sizeof(bitblock128_t)/sizeof(uint32_t)];
     20        uint16_t _16[sizeof(bitblock128_t)/sizeof(uint16_t)];
     21        uint8_t _8[sizeof(bitblock128_t)/sizeof(uint8_t)];
     22};
     23
    1424static IDISA_ALWAYS_INLINE void adc(bitblock128_t x, bitblock128_t y, bitblock128_t & carry, bitblock128_t & sum);
    1525static IDISA_ALWAYS_INLINE void sbb(bitblock128_t x, bitblock128_t y, bitblock128_t & borrow, bitblock128_t & difference);
     
    2030static IDISA_ALWAYS_INLINE bitblock128_t convert (uint64_t s);
    2131static IDISA_ALWAYS_INLINE uint64_t convert (bitblock128_t v);
     32static IDISA_ALWAYS_INLINE uint32_t count_forward_zeroes(bitblock128_t v);
     33static IDISA_ALWAYS_INLINE uint32_t count_backward_zeroes(bitblock128_t v);
     34
    2235
    2336IDISA_ALWAYS_INLINE void adc(bitblock128_t x, bitblock128_t y, bitblock128_t & carry, bitblock128_t & sum)
     
    2538        bitblock128_t gen = simd_and(x, y);
    2639        bitblock128_t prop = simd_or(x, y);
    27         bitblock128_t partial = simd<64>::add(simd<64>::add(x, y), carry);
    28         bitblock128_t c1 = simd128<128>::slli<64>(simd<64>::srli<63>(simd_or(gen, simd_andc(prop, partial))));
    29         sum = simd<64>::add(c1, partial);
     40        bitblock128_t partial = simd128<64>::add(simd128<64>::add(x, y), carry);
     41        bitblock128_t c1 = simd128<128>::slli<64>(simd128<64>::srli<63>(simd_or(gen, simd_andc(prop, partial))));
     42        sum = simd128<64>::add(c1, partial);
    3043        // carry = simd_and(hibitmask<bitblock128_t>(), simd_or(gen, simd_andc(prop, sum))); // TODO - set high bit carry via hibitmask
    3144        carry = simd128<128>::srli<127>(simd_or(gen, simd_andc(prop, sum))); // TODO -
     
    3649        bitblock128_t gen = simd_andc(y, x);
    3750        bitblock128_t prop = simd_not(simd_xor(x, y));
    38         bitblock128_t partial = simd<64>::sub(simd<64>::sub(x, y), borrow);
    39         bitblock128_t b1 = simd128<128>::slli<64>(simd<64>::srli<63>(simd_or(gen, simd_and(prop, partial))));
    40         difference = simd<64>::sub(partial, b1);
     51        bitblock128_t partial = simd128<64>::sub(simd128<64>::sub(x, y), borrow);
     52        bitblock128_t b1 = simd128<128>::slli<64>(simd128<64>::srli<63>(simd_or(gen, simd_and(prop, partial))));
     53        difference = simd128<64>::sub(partial, b1);
    4154        // borrow = simd_and(hibitmask<bitblock128_t>, simd_or(gen, simd_and(prop, difference))); // TODO - set high bit carry via hibitmask
    4255        borrow = simd128<128>::srli<127>(simd_or(gen, simd_and(prop, difference)));
     
    4558IDISA_ALWAYS_INLINE void advance_with_carry(bitblock128_t cursor, bitblock128_t & carry, bitblock128_t & rslt)
    4659{
    47 bitblock128_t shift_out = simd<64>::srli<63>(cursor);
    48 bitblock128_t low_bits = esimd<64>::mergel(shift_out, carry);
     60bitblock128_t shift_out = simd128<64>::srli<63>(cursor);
     61bitblock128_t low_bits = esimd128<64>::mergel(shift_out, carry);
    4962// carry = simd_and(hibitmask<bitblock128_t>, cursor);
    5063carry = simd128<128>::srli<64>(shift_out);                                              // carry - accumlated 127 shift right locical shift of cursor
    51 rslt = simd_or(simd<64>::add(cursor, cursor), low_bits);
     64rslt = simd_or(simd128<64>::add(cursor, cursor), low_bits);
    5265}
    5366
    5467IDISA_ALWAYS_INLINE bool bitblock_has_bit(bitblock128_t arg1)
    5568{
    56         // TOOD simd128::any(arg1);
    5769        return bitblock::any(arg1);
    5870}
     
    6072IDISA_ALWAYS_INLINE uint64_t bitblock_bit_count(bitblock128_t arg1)
    6173{
    62         // TODO simd128::popcount(arg1)
    63         return mvmd<64>::extract<0>(simd128<128>::popcount(arg1));
     74        return mvmd128<64>::extract<0>(simd128<128>::popcount(arg1));
    6475}
    6576
    6677IDISA_ALWAYS_INLINE void signbitmask(bitblock128_t & v)
    6778{
    68         // TODO simd128::
    6979        v =  simd128<128>::slli<127>(simd128<128>::constant<1>());
    7080}
    71 
    72 /* Type conversion support */
    73 union ubitblock128 {
    74         //bitblock256_t 256;
    75         bitblock128_t _128;
    76         uint64_t _64[sizeof(bitblock128_t)/sizeof(uint64_t)];
    77         uint32_t _32[sizeof(bitblock128_t)/sizeof(uint32_t)];
    78         uint16_t _16[sizeof(bitblock128_t)/sizeof(uint16_t)];
    79         uint8_t _8[sizeof(bitblock128_t)/sizeof(uint8_t)];
    80 };
    8181
    8282IDISA_ALWAYS_INLINE bitblock128_t convert(uint64_t s)
     
    8989IDISA_ALWAYS_INLINE uint64_t convert (bitblock128_t v)
    9090{
    91         return (uint64_t) mvmd<64>::extract<0>(v);
     91        return (uint64_t) mvmd128<64>::extract<0>(v);
    9292}
    9393
     94IDISA_ALWAYS_INLINE uint32_t count_forward_zeroes(bitblock128_t v) {
     95        union {bitblock128_t bitblock; unsigned long elems[sizeof(bitblock128_t)/sizeof(long)];} u;
     96        u.bitblock = v;
     97
     98#if LONG_BIT == 64
     99  if (u.elems[0] != 0) {return cfzll(u.elems[0]);}
     100  else if (u.elems[1] != 0) {return 64 + cfzll(u.elems[1]);}
     101  else {return 128;}
     102#endif
     103
     104#if LONG_BIT < 64
     105  if (u.elems[0] != 0) {return cfzl(u.elems[0]);}
     106  else if (u.elems[1] != 0) {return 32 + cfzl(u.elems[1]);}
     107  else if (u.elems[2] != 0) {return 64 + cfzl(u.elems[2]);}
     108  else if (u.elems[3] != 0) {return 96 + cfzl(u.elems[3]);}
     109#endif
     110  else {return 128;}
     111}
     112
     113IDISA_ALWAYS_INLINE uint32_t count_backward_zeroes(bitblock128_t v) {
     114        union {bitblock128_t bitblock; unsigned long elems[sizeof(bitblock128_t)/sizeof(long)];} u;
     115        u.bitblock = v;
     116
     117#if LONG_BIT == 64
     118  if (u.elems[1] != 0) return cbzll(u.elems[1]);
     119  else if (u.elems[0] != 0) return LONG_BIT + cbzll(u.elems[0]);
     120#endif
     121#if LONG_BIT < 64
     122  if (u.elems[3] != 0) return cbzl(u.elems[3]);
     123  else if (u.elems[2] != 0) return 32 + cbzl(u.elems[2]);
     124  else if (u.elems[1] != 0) return 64 + cbzl(u.elems[1]);
     125  else if (u.elems[0] != 0) return 96 + cbzl(u.elems[0]);
     126#endif
     127  else {return 128;}
     128}
    94129
    95130#endif /* BITBLOCK128_HPP_ */
  • trunk/lib/bitblock256.hpp

    r1542 r1550  
    11/*
    2     bitblock256 - 256 bit block size - Specific 256 bit implementations.
     2    bitblock256 - Specific 256 bit IDISA implementations.
    33
    44    Idealized SIMD Operations with SSE versions
     
    1313#define BITBLOCK256_HPP_
    1414
     15#include "idisa128.hpp"
     16#include "idisa256.hpp"
     17
     18union ubitblock256 {
     19        bitblock128_t _256;
     20        bitblock128_t _128[sizeof(bitblock256_t)/sizeof(bitblock128_t)];
     21        uint64_t _64[sizeof(bitblock128_t)/sizeof(uint64_t)];
     22        uint32_t _32[sizeof(bitblock128_t)/sizeof(uint32_t)];
     23        uint16_t _16[sizeof(bitblock128_t)/sizeof(uint16_t)];
     24        uint8_t _8[sizeof(bitblock128_t)/sizeof(uint8_t)];
     25};
    1526
    1627#endif /* BITBLOCK256_HPP_ */
  • trunk/lib/builtins.hpp

    r1528 r1550  
    1414#include "config.hpp"
    1515
    16 static IDISA_INLINE long likely(long x);
    17 static IDISA_INLINE long unlikely(long x);
    18 static IDISA_INLINE unsigned long cfzl(unsigned long x) IDISA_ALWAYS_INLINE;
    19 static IDISA_INLINE unsigned long cbzl(unsigned long x) IDISA_ALWAYS_INLINE;
    20 static IDISA_INLINE unsigned long cfzll(unsigned long x) IDISA_ALWAYS_INLINE;
    21 static IDISA_INLINE unsigned long cbzll(unsigned long x) IDISA_ALWAYS_INLINE;
     16static IDISA_ALWAYS_INLINE long likely(long x);
     17static IDISA_ALWAYS_INLINE long unlikely(long x);
     18static IDISA_ALWAYS_INLINE unsigned long cfzl(unsigned long x);
     19static IDISA_ALWAYS_INLINE unsigned long cbzl(unsigned long x);
     20static IDISA_ALWAYS_INLINE unsigned long cfzll(unsigned long long x);
     21static IDISA_ALWAYS_INLINE unsigned long cbzll(unsigned long long x);
    2222
    2323#if defined (_MSC_VER)
    24         static IDISA_INLINE long likely(long x) {
     24        IDISA_ALWAYS_INLINE long likely(long x) {
    2525                return x;
    2626        }
    27         static IDISA_INLINE long unlikely(long x) {
     27        IDISA_ALWAYS_INLINE long unlikely(long x) {
    2828                return x;
    2929        }
     
    3131        #include <intrin.h>
    3232        #pragma intrinsic(_BitScanForward)
    33         static IDISA_INLINE unsigned long cfzl(unsigned long x) { // Precondition: x > 0
     33        IDISA_ALWAYS_INLINE unsigned long cfzl(unsigned long x) { // Precondition: x > 0
    3434                unsigned long zeroes;
    3535                _BitScanForward(&zeroes, x);
     
    3737        }
    3838
    39         static IDISA_INLINE unsigned long cbzl(unsigned long x) {
     39        IDISA_ALWAYS_INLINE unsigned long cbzl(unsigned long x) {
    4040                unsigned long zeroes;
    4141                _BitScanReverse(&zeroes, x);
     
    4343        }
    4444
    45         static IDISA_INLINE unsigned long cfzll(unsigned long long x) { // TODO - test
     45        IDISA_ALWAYS_INLINE unsigned long cfzll(unsigned long long x) { // TODO - test
    4646                unsigned __int64 zeroes;
    4747                _BitScanForward(&zeroes, x);
     
    4949        }
    5050
    51         static IDISA_INLINE unsigned long cbzll(unsigned long long x) { // TODO - test
     51        IDISA_ALWAYS_INLINE unsigned long cbzll(unsigned long long x) { // TODO - test
    5252                unsigned __int64 zeroes;
    5353                _BitScanReverse(&zeroes, x);
     
    5656
    5757#elif defined (__GNUC__)
    58         static IDISA_INLINE long likely(long x) {
     58
     59        IDISA_ALWAYS_INLINE long likely(long x) {
    5960                return __builtin_expect(x, 1);
    6061        }
    6162
    62         static IDISA_INLINE long unlikely(long x) {
     63        IDISA_ALWAYS_INLINE long unlikely(long x) {
    6364                return __builtin_expect(x, 0);
    6465        }
    6566
    66         static IDISA_INLINE unsigned long cfzl(unsigned long x) {
     67        IDISA_ALWAYS_INLINE unsigned long cfzl(unsigned long x) {
    6768                return __builtin_ctzl(x);
    6869        }
    6970
    70         static IDISA_INLINE unsigned long cbzl(unsigned long x) {
     71        IDISA_ALWAYS_INLINE unsigned long cbzl(unsigned long x) {
    7172                return __builtin_clzl(x);
    7273        }
    7374
    74         static IDISA_INLINE unsigned long cfzll(unsigned long long x) {
     75        IDISA_ALWAYS_INLINE unsigned long cfzll(unsigned long long x) {
    7576                return __builtin_ctzll(x);
    7677        }
    7778
    78         static IDISA_INLINE unsigned long cbzll(unsigned long long x) {
     79        IDISA_ALWAYS_INLINE unsigned long cbzll(unsigned long long x) {
    7980                return __builtin_clzll(x);
    8081        }
Note: See TracChangeset for help on using the changeset viewer.