source: trunk/lib/bitblock128.hpp @ 1555

Last change on this file since 1555 was 1555, checked in by ksherdy, 8 years ago

Move #include builtins.hpp.

File size: 5.6 KB
Line 
1/*
2    bitblock128 - Specific 128 bit IDISA implementations.
3
4    Idealized SIMD Operations with SSE versions
5    Copyright (C) 2011, Robert D. Cameron, Kenneth S. Herdy, Hua Huang and Nigel Medforth.
6    Licensed to the public under the Open Software License 3.0.
7    Licensed to International Characters Inc.
8       under the Academic Free License version 3.0.
9
10*/
11#ifndef BITBLOCK128_HPP_
12#define BITBLOCK128_HPP_
13
14#include "idisa128.hpp"
15#include "builtins.hpp"
16
17union ubitblock128 {
18        bitblock128_t _128;
19        uint64_t _64[sizeof(bitblock128_t)/sizeof(uint64_t)];
20        uint32_t _32[sizeof(bitblock128_t)/sizeof(uint32_t)];
21        uint16_t _16[sizeof(bitblock128_t)/sizeof(uint16_t)];
22        uint8_t _8[sizeof(bitblock128_t)/sizeof(uint8_t)];
23};
24
25static IDISA_ALWAYS_INLINE void adc(bitblock128_t x, bitblock128_t y, bitblock128_t & carry, bitblock128_t & sum);
26static IDISA_ALWAYS_INLINE void sbb(bitblock128_t x, bitblock128_t y, bitblock128_t & borrow, bitblock128_t & difference);
27static IDISA_ALWAYS_INLINE void advance_with_carry(bitblock128_t cursor, bitblock128_t & carry, bitblock128_t & rslt);
28static IDISA_ALWAYS_INLINE bool bitblock_has_bit(bitblock128_t arg1);
29static IDISA_ALWAYS_INLINE uint64_t bitblock_bit_count(bitblock128_t arg1);
30static IDISA_ALWAYS_INLINE void signbitmask(bitblock128_t & v);
31static IDISA_ALWAYS_INLINE bitblock128_t convert (uint64_t s);
32static IDISA_ALWAYS_INLINE uint64_t convert (bitblock128_t v);
33static IDISA_ALWAYS_INLINE uint32_t count_forward_zeroes(bitblock128_t v);
34static IDISA_ALWAYS_INLINE uint32_t count_backward_zeroes(bitblock128_t v);
35static IDISA_ALWAYS_INLINE uint32_t bitstream_scan(bitblock128_t * v, uint32_t pos);
36
37IDISA_ALWAYS_INLINE void adc(bitblock128_t x, bitblock128_t y, bitblock128_t & carry, bitblock128_t & sum)
38{
39        bitblock128_t gen = simd_and(x, y);
40        bitblock128_t prop = simd_or(x, y);
41        bitblock128_t partial = simd128<64>::add(simd128<64>::add(x, y), carry);
42        bitblock128_t c1 = simd128<128>::slli<64>(simd128<64>::srli<63>(simd_or(gen, simd_andc(prop, partial))));
43        sum = simd128<64>::add(c1, partial);
44        // carry = simd_and(hibitmask<bitblock128_t>(), simd_or(gen, simd_andc(prop, sum))); // TODO - set high bit carry via hibitmask
45        carry = simd128<128>::srli<127>(simd_or(gen, simd_andc(prop, sum))); // TODO -
46}
47
48IDISA_ALWAYS_INLINE void sbb(bitblock128_t x, bitblock128_t y, bitblock128_t & borrow, bitblock128_t & difference)
49{
50        bitblock128_t gen = simd_andc(y, x);
51        bitblock128_t prop = simd_not(simd_xor(x, y));
52        bitblock128_t partial = simd128<64>::sub(simd128<64>::sub(x, y), borrow);
53        bitblock128_t b1 = simd128<128>::slli<64>(simd128<64>::srli<63>(simd_or(gen, simd_and(prop, partial))));
54        difference = simd128<64>::sub(partial, b1);
55        // borrow = simd_and(hibitmask<bitblock128_t>, simd_or(gen, simd_and(prop, difference))); // TODO - set high bit carry via hibitmask
56        borrow = simd128<128>::srli<127>(simd_or(gen, simd_and(prop, difference)));
57}
58
59IDISA_ALWAYS_INLINE void advance_with_carry(bitblock128_t cursor, bitblock128_t & carry, bitblock128_t & rslt)
60{
61bitblock128_t shift_out = simd128<64>::srli<63>(cursor);
62bitblock128_t low_bits = esimd128<64>::mergel(shift_out, carry);
63// carry = simd_and(hibitmask<bitblock128_t>, cursor);
64carry = simd128<128>::srli<64>(shift_out);                                              // carry - accumlated 127 shift right locical shift of cursor
65rslt = simd_or(simd128<64>::add(cursor, cursor), low_bits);
66}
67
68IDISA_ALWAYS_INLINE bool bitblock_has_bit(bitblock128_t arg1)
69{
70        return bitblock::any(arg1);
71}
72
73IDISA_ALWAYS_INLINE uint64_t bitblock_bit_count(bitblock128_t arg1)
74{
75        return mvmd128<64>::extract<0>(simd128<128>::popcount(arg1));
76}
77
78IDISA_ALWAYS_INLINE void signbitmask(bitblock128_t & v)
79{
80        v =  simd128<128>::slli<127>(simd128<128>::constant<1>());
81}
82
83IDISA_ALWAYS_INLINE bitblock128_t convert(uint64_t s)
84{
85        ubitblock128 b = {b._128 = simd128<128>::constant<0>()}; // = {0};
86        b._64[0] = s;
87        return b._128;
88}
89
90IDISA_ALWAYS_INLINE uint64_t convert (bitblock128_t v)
91{
92        return (uint64_t) mvmd128<64>::extract<0>(v);
93}
94
95IDISA_ALWAYS_INLINE uint32_t count_forward_zeroes(bitblock128_t v) {
96        union {bitblock128_t bitblock; unsigned long elems[sizeof(bitblock128_t)/sizeof(long)];} u;
97        u.bitblock = v;
98
99#if LONG_BIT == 64
100  if (u.elems[0] != 0) {return cfzll(u.elems[0]);}
101  else if (u.elems[1] != 0) {return 64 + cfzll(u.elems[1]);}
102  else {return 128;}
103#endif
104
105#if LONG_BIT < 64
106  if (u.elems[0] != 0) {return cfzl(u.elems[0]);}
107  else if (u.elems[1] != 0) {return 32 + cfzl(u.elems[1]);}
108  else if (u.elems[2] != 0) {return 64 + cfzl(u.elems[2]);}
109  else if (u.elems[3] != 0) {return 96 + cfzl(u.elems[3]);}
110#endif
111  else {return 128;}
112}
113
114IDISA_ALWAYS_INLINE uint32_t count_backward_zeroes(bitblock128_t v) {
115        union {bitblock128_t bitblock; unsigned long elems[sizeof(bitblock128_t)/sizeof(long)];} u;
116        u.bitblock = v;
117
118#if LONG_BIT == 64
119  if (u.elems[1] != 0) return cbzll(u.elems[1]);
120  else if (u.elems[0] != 0) return LONG_BIT + cbzll(u.elems[0]);
121#endif
122#if LONG_BIT < 64
123  if (u.elems[3] != 0) return cbzl(u.elems[3]);
124  else if (u.elems[2] != 0) return 32 + cbzl(u.elems[2]);
125  else if (u.elems[1] != 0) return 64 + cbzl(u.elems[1]);
126  else if (u.elems[0] != 0) return 96 + cbzl(u.elems[0]);
127#endif
128  else {return 128;}
129}
130
131IDISA_ALWAYS_INLINE uint32_t bitstream_scan(bitblock128_t * v, uint32_t pos) {
132  unsigned long * bitstream_ptr = (unsigned long *) (((intptr_t) v) + pos/8);
133  unsigned long bitstream_slice = ((*bitstream_ptr) >> (pos % 8));
134  if (bitstream_slice != 0) return pos + cfzl(bitstream_slice);
135  else {
136    do {
137      bitstream_ptr++;
138      bitstream_slice = *bitstream_ptr;
139    } while (bitstream_slice == 0);
140    uint32_t base_posn = 8*((intptr_t) bitstream_ptr - (intptr_t) v);
141    return base_posn + cfzl(bitstream_slice);
142  }
143}
144
145
146#endif /* BITBLOCK128_HPP_ */
Note: See TracBrowser for help on using the repository browser.