sux 0.12.3

A pure Rust implementation of succinct and compressed data structures
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

/**
 * This code is released under the
 * Apache License Version 2.0 http://www.apache.org/licenses/.
 */

/*  Based on code by
 *      Takeshi Yamamuro <linguin.m.s_at_gmail.com>
 *      Fabrizio Silvestri <fabrizio.silvestri_at_isti.cnr.it>
 *      Rossano Venturini <rossano.venturini_at_isti.cnr.it>
 *   which was available  under the Apache License, Version 2.0.
 */

#ifndef SIMDOPTPFOR_H_
#define SIMDOPTPFOR_H_

#include "common.h"
#include "util.h"
#include "simple16.h"
#include "simdnewpfor.h"

namespace FastPFor {

/**
 * SIMDOptPFor, a SIMD-version of OPTPFor designed by D. Lemire
 *
 * In a multithreaded context, you may need one OPTPFor per thread.
 *
 * Combines results from the following papers:
 *
 * H. Yan, S. Ding, T. Suel, Inverted index compression and query processing with
 * optimized document ordering, in: WWW '09, 2009, pp. 401-410.
 *
 * Daniel Lemire and Leonid Boytsov, Decoding billions of integers per second through std::vectorization
 * Software: Practice & Experience
 * http://arxiv.org/abs/1209.2137
 * http://onlinelibrary.wiley.com/doi/10.1002/spe.2203/abstract
 */
template<uint32_t BlockSizeInUnitsOfPackSize, class ExceptionCoder = Simple16<
        false> >
class SIMDOPTPFor: public SIMDNewPFor<BlockSizeInUnitsOfPackSize, ExceptionCoder> {
public:

    SIMDOPTPFor()  {
    }
    uint32_t tryB(uint32_t b, const uint32_t *in, uint32_t len);
    uint32_t findBestB(const uint32_t *in, uint32_t len);

    virtual std::string name() const {
        std::ostringstream convert;
        convert << "SIMDOPTPFor<" << BlockSizeInUnitsOfPackSize << "," << SIMDNewPFor<
                BlockSizeInUnitsOfPackSize, ExceptionCoder>::ecoder.name()
                << ">";
        return convert.str();
    }
};

template<uint32_t BlockSizeInUnitsOfPackSize, class ExceptionCoder>
__attribute__ ((pure))
uint32_t SIMDOPTPFor<BlockSizeInUnitsOfPackSize, ExceptionCoder>::tryB(uint32_t b,
        const uint32_t *in, uint32_t len) {

    assert(b <= 32);
    if (b == 32) {
        return len;
    }
    uint32_t size = div_roundup(len * b, 32);
    uint32_t curExcept = 0;

    for (uint32_t i = 0; i < len; i++) {
        if (in[i] >= (1U << b)) {
            const uint32_t e = in[i] >> b;
            SIMDNewPFor<BlockSizeInUnitsOfPackSize, ExceptionCoder>::exceptionsPositions[curExcept]
                    = i;
            SIMDNewPFor<BlockSizeInUnitsOfPackSize, ExceptionCoder>::exceptionsValues[curExcept]
                    = e;
            curExcept++;
        }
    }

    if (curExcept > 0) {

        for (uint32_t i = curExcept - 1; i > 0; i--) {
            const uint32_t cur = SIMDNewPFor<BlockSizeInUnitsOfPackSize,
                    ExceptionCoder>::exceptionsPositions[i];
            const uint32_t prev = SIMDNewPFor<BlockSizeInUnitsOfPackSize,
                    ExceptionCoder>::exceptionsPositions[i - 1];
            const uint32_t gap = cur - prev;
            SIMDNewPFor<BlockSizeInUnitsOfPackSize, ExceptionCoder>::exceptionsPositions[i]
                    = gap;
        }

        for (uint32_t i = 0; i < curExcept; i++) {
            const uint32_t excPos =
                    (i > 0) ? SIMDNewPFor<BlockSizeInUnitsOfPackSize,
                            ExceptionCoder>::exceptionsPositions[i] - 1
                            : SIMDNewPFor<BlockSizeInUnitsOfPackSize,
                                    ExceptionCoder>::exceptionsPositions[i];
            const uint32_t excVal = SIMDNewPFor<BlockSizeInUnitsOfPackSize,
                    ExceptionCoder>::exceptionsValues[i] - 1;
            SIMDNewPFor<BlockSizeInUnitsOfPackSize, ExceptionCoder>::exceptions[i]
                    = excPos;
            SIMDNewPFor<BlockSizeInUnitsOfPackSize, ExceptionCoder>::exceptions[i
                    + curExcept] = excVal;
        }
        size_t encodedExceptions_sz;
        SIMDNewPFor<BlockSizeInUnitsOfPackSize, ExceptionCoder>::ecoder.fakeencodeArray(
                &SIMDNewPFor<BlockSizeInUnitsOfPackSize, ExceptionCoder>::exceptions[0],
                2 * curExcept, /*&encodedExceptions[0], */encodedExceptions_sz);
        size += static_cast<uint32_t>(encodedExceptions_sz);
    }
    return size;

}
template<uint32_t BlockSizeInUnitsOfPackSize, class ExceptionCoder>
__attribute__ ((pure))
uint32_t SIMDOPTPFor<BlockSizeInUnitsOfPackSize, ExceptionCoder>::findBestB(
        const uint32_t *in, uint32_t len) {
    uint32_t
            b =
            		SIMDNewPFor<BlockSizeInUnitsOfPackSize, ExceptionCoder>::possLogs.back();
    assert(b == 32);
    uint32_t bsize = tryB(b, in, len);
    const uint32_t mb = maxbits(in,in+len);
    uint32_t i = 0;
    while(mb  > 28 + SIMDNewPFor<BlockSizeInUnitsOfPackSize, ExceptionCoder>::possLogs[i]) ++i; // some schemes such as Simple16 don't code numbers greater than 28

    for (; i
            < SIMDNewPFor<BlockSizeInUnitsOfPackSize, ExceptionCoder>::possLogs.size()
                    - 1; i++) {
        const uint32_t
                csize =
                        tryB(
                                SIMDNewPFor<BlockSizeInUnitsOfPackSize,
                                        ExceptionCoder>::possLogs[i], in, len);

        if (csize <= bsize) {
            b
                    = SIMDNewPFor<BlockSizeInUnitsOfPackSize, ExceptionCoder>::possLogs[i];
            bsize = csize;
        }
    }
    return b;
}

} // namespace FastPFor

#endif /* SIMDOPTPFOR_H_ */