source: trunk/lib/bitblock.hpp @ 2614

Last change on this file since 2614 was 2614, checked in by ksherdy, 7 years ago

Nobody will ever need anymore than 64k of memory.

File size: 4.0 KB
Line 
1#ifndef BITBLOCK_HPP
2#define BITBLOCK_HPP
3
4/*=============================================================================
5        IDISA Library Import - Generic
6        Copyright (C) 2011, Robert D. Cameron, Kenneth S. Herdy
7        Licensed to the public under the Open Software License 3.0.
8        Licensed to International Characters Inc.
9           under the Academic Free License version 3.0.
10=============================================================================*/
11
12// #define NDEBUG // if NDEBUG then disable assertions
13
14#define __STDC_LIMIT_MACROS
15#include <stdint.h>
16#include <stdio.h>
17#include <cassert>
18
19#include "config.hpp"
20#include "builtins.hpp"
21#include "idisa.hpp"
22
23#define BytePack BitBlock
24#ifndef BLOCK_SIZE
25#define BLOCK_SIZE 128
26#endif
27#ifndef ATTRIBUTE_SIMD_ALIGN
28        #if defined _MSC_VER
29                //note: MSVC++ cannot accept sizeof or division within __declspec(align(...))
30                #define ATTRIBUTE_SIMD_ALIGN __declspec(align(16))
31        #elif defined __GNUC__
32                #define ATTRIBUTE_SIMD_ALIGN __attribute__((aligned(sizeof(BitBlock))))
33        #else
34                #define ATTRIBUTE_SIMD_ALIGN
35        #endif
36#endif
37
38template<class T> void print_register(const char * var_name, T v);
39
40static IDISA_ALWAYS_INLINE uint32_t count_forward_zeroes(BitBlock v);
41static IDISA_ALWAYS_INLINE uint32_t count_reverse_zeroes(BitBlock v);
42static IDISA_ALWAYS_INLINE BitBlock mask_forward_zeroes(uint32_t count);
43static IDISA_ALWAYS_INLINE BitBlock mask_reverse_zeroes(uint32_t count);
44static IDISA_ALWAYS_INLINE uint32_t bitstream_scan(BitBlock * v, uint32_t pos);
45
46/*  BitBlock union type */
47union ubitblock;
48
49/*  Default BLOCK_SIZE is 128, compatible with SSE, Altivec, SPU */
50#if (BLOCK_SIZE == 128)
51#include "bitblock128.hpp"
52#endif
53
54/*  BLOCK_SIZE 256 for AVX */
55#if (BLOCK_SIZE == 256)
56#include "bitblock256.hpp"
57#endif
58
59template <class T> void print_register(const char * var_name, T v);
60template <class T>
61void print_register(const char * var_name, T v) {
62        unsigned char c;
63        printf("%40s = ", var_name);
64        for(int i=sizeof(T)-1; i>=0; i--) {
65                c = *(((unsigned char *)&v)+i);
66                printf("%02X ", c);
67        }
68        printf("\n");
69}
70
71IDISA_ALWAYS_INLINE uint32_t count_forward_zeroes(BitBlock v) {
72        union {BitBlock bitblock; ScanWord elems[sizeof(BitBlock)/sizeof(ScanWord)];} u;
73        u.bitblock = v;
74        uint32_t so_far = 0;
75        for (unsigned int i = 0; i < sizeof(BitBlock)/sizeof(ScanWord); i++) {
76                if (u.elems[i] != 0) return so_far | scan_forward_zeroes(u.elems[i]);
77                so_far += 8 * sizeof(ScanWord);
78        }
79        return so_far;
80}
81
82IDISA_ALWAYS_INLINE BitBlock mask_forward_zeroes(uint32_t count) {
83        if (count >= sizeof(BitBlock) * 8) return simd<1>::constant<0>();
84                else return bitblock::sll(simd<1>::constant<1>(), convert(count));
85}
86
87IDISA_ALWAYS_INLINE uint32_t count_reverse_zeroes(BitBlock v) {
88        union {BitBlock bitblock; ScanWord elems[sizeof(BitBlock)/sizeof(ScanWord)];} u;
89        u.bitblock = v;
90        uint32_t so_far = 0;
91        for (unsigned int i = (sizeof(BitBlock)/sizeof(ScanWord)); i != 0; ) {
92                if (u.elems[--i] != 0) return so_far | scan_backward_zeroes(u.elems[i]);
93                so_far += 8 * sizeof(ScanWord);
94        }
95        return so_far;
96}
97
98IDISA_ALWAYS_INLINE BitBlock mask_reverse_zeroes(uint32_t count) {
99        if (count >= sizeof(BitBlock) * 8) return simd<1>::constant<0>();
100                else return bitblock::srl(simd<1>::constant<1>(), convert(count));
101}
102
103IDISA_ALWAYS_INLINE uint32_t bitstream_scan(BitBlock * v, uint32_t pos) {
104        ScanWord * bitstream_ptr = (ScanWord *) (((intptr_t) v) + pos/8);
105        ScanWord bitstream_slice = ((*bitstream_ptr) >> (pos % 8));
106        if (bitstream_slice != 0) return pos + scan_forward_zeroes(bitstream_slice);
107        else {
108                do {
109                        bitstream_ptr++;
110                        bitstream_slice = *bitstream_ptr;
111                } while (bitstream_slice == 0);
112                uint32_t base_posn = 8*((intptr_t) bitstream_ptr - (intptr_t) v);
113                return base_posn + scan_forward_zeroes(bitstream_slice);
114        }
115}
116
117static IDISA_ALWAYS_INLINE void assert_bitblock_align(void * addr) {
118        assert(0 == ((intptr_t)(addr) & (sizeof(BitBlock)-1)));
119}
120
121static IDISA_ALWAYS_INLINE void assert_bitblock_align(BitBlock v) {
122        assert(0 == ((intptr_t)(&v) & (sizeof(BitBlock)-1)));
123}
124
125#define ASSERT_BITBLOCK_ALIGN(v) assert_bitblock_align(v)
126
127#endif // BITBLOCK_HPP
128
129
Note: See TracBrowser for help on using the repository browser.