source: trunk/lib/bitblock.hpp @ 2037

Last change on this file since 2037 was 2037, checked in by cameron, 7 years ago

Add mask_forward_zeroes/mask_reverse_zeroes

File size: 3.8 KB
RevLine 
[1950]1#ifndef BITBLOCK_HPP
2#define BITBLOCK_HPP
3
4/*=============================================================================
[1500]5    IDISA Library Import - Generic
[1617]6    Copyright (C) 2011, Robert D. Cameron, Kenneth S. Herdy
[1500]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.
[1950]10=============================================================================*/
[1500]11
[1970]12#define NDEBUG //if NDEBUG then disable assertions
[1903]13
[1874]14#define __STDC_LIMIT_MACROS
[1542]15#include <stdint.h>
16#include <stdio.h>
[1898]17#include <cassert>
18
[1542]19#include "config.hpp"
[1617]20#include "builtins.hpp"
[1542]21#include "idisa.hpp"
22
[1808]23#define BytePack BitBlock
[1576]24#ifndef BLOCK_SIZE
25#define BLOCK_SIZE 128
[1500]26#endif
[1933]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
[1500]37
[1617]38template<class T> void print_register(const char * var_name, T v);
39
[1890]40static IDISA_ALWAYS_INLINE uint32_t count_forward_zeroes(BitBlock v);
41static IDISA_ALWAYS_INLINE uint32_t count_reverse_zeroes(BitBlock v);
[2037]42static IDISA_ALWAYS_INLINE BitBlock mask_forward_zeroes(uint32_t count);
43static IDISA_ALWAYS_INLINE BitBlock mask_reverse_zeroes(uint32_t count);
[1890]44static IDISA_ALWAYS_INLINE uint32_t bitstream_scan(BitBlock * v, uint32_t pos);
[1898]45static IDISA_ALWAYS_INLINE BitBlock assert_align(BitBlock v);
[1890]46
[1815]47/*  BitBlock union type */
48union ubitblock;
49
[1576]50/*  Default BLOCK_SIZE is 128, compatible with SSE, Altivec, SPU */
51#if (BLOCK_SIZE == 128)
[1527]52#include "bitblock128.hpp"
[1500]53#endif
54
[1576]55/*  BLOCK_SIZE 256 for AVX */
56#if (BLOCK_SIZE == 256)
[1527]57#include "bitblock256.hpp"
[1500]58#endif
59
[1658]60template <class T> void print_register(const char * var_name, T v);
[1527]61template <class T>
62void print_register(const char * var_name, T v) {
63        unsigned char c;
64        printf("%20s = ", var_name);
65        for(int i=sizeof(T)-1; i>=0; i--) {
66                c = *(((unsigned char *)&v)+i);
67                printf("%02X ", c);
68        }
69        printf("\n");
70}
71
[1890]72IDISA_ALWAYS_INLINE uint32_t count_forward_zeroes(BitBlock v) {
73        union {BitBlock bitblock; scanword_t elems[sizeof(BitBlock)/sizeof(scanword_t)];} u;
74        u.bitblock = v;
75        uint32_t so_far = 0;
76        for (int i = 0; i < sizeof(BitBlock)/sizeof(scanword_t); i++) {
77                if (u.elems[i] != 0) return so_far + scan_forward_zeroes(u.elems[i]);
78                so_far += 8 * sizeof(scanword_t);
79        }
80        return so_far;
81}
82
[2037]83IDISA_ALWAYS_INLINE BitBlock mask_forward_zeroes(uint32_t count) {
84        if (count >= sizeof(BitBlock) * 8) return simd<1>::constant<0>();
85        else return bitblock::sll(simd<1>::constant<1>(), convert(count));
86}
87
[1890]88IDISA_ALWAYS_INLINE uint32_t count_reverse_zeroes(BitBlock v) {
89        union {BitBlock bitblock; scanword_t elems[sizeof(BitBlock)/sizeof(scanword_t)];} u;
90        u.bitblock = v;
91        uint32_t so_far = 0;
92        for (int i = sizeof(BitBlock)/sizeof(scanword_t) - 1; i >= 0; i--) {
93                if (u.elems[i] != 0) return so_far + scan_backward_zeroes(u.elems[i]);
94                so_far += 8 * sizeof(scanword_t);
95        }
96        return so_far;
97}
98
[2037]99IDISA_ALWAYS_INLINE BitBlock mask_reverse_zeroes(uint32_t count) {
100        if (count >= sizeof(BitBlock) * 8) return simd<1>::constant<0>();
101        else return bitblock::srl(simd<1>::constant<1>(), convert(count));
102}
103
[1890]104IDISA_ALWAYS_INLINE uint32_t bitstream_scan(BitBlock * v, uint32_t pos) {
105        scanword_t * bitstream_ptr = (scanword_t *) (((intptr_t) v) + pos/8);
106        scanword_t bitstream_slice = ((*bitstream_ptr) >> (pos % 8));
107        if (bitstream_slice != 0) return pos + scan_forward_zeroes(bitstream_slice);
108        else {
109                do {
110                        bitstream_ptr++;
111                        bitstream_slice = *bitstream_ptr;
112                } while (bitstream_slice == 0);
113                uint32_t base_posn = 8*((intptr_t) bitstream_ptr - (intptr_t) v);
114                return base_posn + scan_forward_zeroes(bitstream_slice);
115        }
116}
117
[1950]118#endif // BITBLOCK_HPP
[1527]119
120
Note: See TracBrowser for help on using the repository browser.