How to compress/decompress sorted array of arbitrary length?

[wshager]

I didn't manage to create a function to successfully decompress a sorted array of arbitrary length. How to do this? I tried several things, including adapting the simdpack_length/simdunpack_length functions to simply use simdpackd1/simdunpackd1. Is this not correct? The function works correctly for 128 integers.

[wshager]

Ah I think this has to do with the offset remaining zero for each new set of 128 integers. Nevermind.

[cruppstahl]

AFAIK there's no way to do that. If you have less than 128 integers then you will have to pad them with garbage, and ignore the garbage when decompressing.

[wshager]

Hmm no it doesn't. The offset is always zero in my sample.

@cruppstahl but if I have 128*2 it should decompress correctly, right?

const __m128i * simdunpackd1_length(uint32_t offset, const __m128i *   in, size_t length, uint32_t * out, const uint32_t bit) {
    size_t k;
    for(k = 0; k < length / SIMDBlockSize; ++k) {
        simdunpackd1(offset, in, out, bit);
        out += SIMDBlockSize;
        in += bit;
    }
    return simdunpack_shortlength(in, length % SIMDBlockSize, out, bit);
}

[cruppstahl]

In my code I only compress blocks of 128 integers with simdunpackd1.

If you compress multiple blocks then you have to make sure that the "bit"
is calculated correctly (for both blocks).

Your code looks ok if the offset is always zero (for all blocks, not just
the first!)

2016-01-26 10:05 GMT+01:00 Wouter Hager notifications@github.com:

Hmm no it doesn't. The offset is always zero in my sample.

@cruppstahl https://github.com/cruppstahl but if I have 128*2 it should
decompress correctly, right?

const __m128i * simdunpackd1_length(uint32_t offset, const __m128i * in,
size_t length, uint32_t * out, const uint32_t bit) {
size_t k;
for(k = 0; k < length / SIMDBlockSize; ++k) {
simdunpackd1(offset, in, out, bit);
out += SIMDBlockSize;
in += bit;
}
return simdunpack_shortlength(in, length % SIMDBlockSize, out, bit);
}

—
Reply to this email directly or view it on GitHub
#15 (comment).

[wshager]

@cruppstahl ah you're right of course. Thanks.

[lemire]

@wshager Is there still an issue or can we close this?