1/*
2 * Copyright (c) 2017, Intel Corporation
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are met:
6 *
7 * * Redistributions of source code must retain the above copyright notice,
8 * this list of conditions and the following disclaimer.
9 * * Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * * Neither the name of Intel Corporation nor the names of its contributors
13 * may be used to endorse or promote products derived from this software
14 * without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/** file
30 * \brief multibit compression API: compress / decompress / size
31 */
32
33#ifndef MULTIBIT_COMPRESS_H
34#define MULTIBIT_COMPRESS_H
35
36#include "multibit.h"
37
38#ifdef __cplusplus
39extern "C" {
40#endif
41
42/** \brief size API. */
43static really_inline
44size_t mmbit_compsize(const u8 *bits, u32 total_bits) {
45 // Deal with flat model.
46 if (total_bits <= MMB_FLAT_MAX_BITS) {
47 return (ROUNDUP_N(total_bits, 8) / 8);
48 }
49 // Deal with all cleared mmb.
50 if (mmb_load(bits) == 0) {
51 return sizeof(MMB_TYPE);
52 }
53 // Deal with normal pyramid mmb.
54 const u32 max_level = mmbit_maxlevel(total_bits);
55 u32 level = 0;
56 u32 key = 0;
57 u32 key_rem = 0;
58 u32 num_block = 0;
59 // Iteration-version of DFS
60 while (1) {
61 if (key_rem < MMB_KEY_BITS) {
62 const u8 *block_ptr = mmbit_get_level_root_const(bits, level) +
63 key * sizeof(MMB_TYPE);
64 MMB_TYPE block = mmb_load(block_ptr);
65 MMB_TYPE block_1 = block & ~mmb_mask_zero_to_nocheck(key_rem);
66 if (mmb_popcount(block) == mmb_popcount(block_1)) {
67 num_block++;
68 }
69 if (level < max_level && block_1) {
70 key = (key << MMB_KEY_SHIFT) + mmb_ctz(block_1);
71 key_rem = 0;
72 level++;
73 continue;
74 }
75 }
76 if (level-- == 0) {
77 return sizeof(MMB_TYPE) * num_block;
78 }
79 key_rem = (key & MMB_KEY_MASK) + 1;
80 key >>= MMB_KEY_SHIFT;
81 }
82}
83
84/** \brief compress API. */
85static really_inline
86char mmbit_compress(const u8 *bits, u32 total_bits, u8 *comp,
87 size_t *comp_space, size_t max_comp_space) {
88 UNUSED u8 *comp_init = comp;
89 // Compute comp_size first.
90 size_t comp_size = mmbit_compsize(bits, total_bits);
91 // Check whether out of writable range.
92 if (comp_size > max_comp_space) {
93 return 0;
94 }
95 *comp_space = comp_size; // Return comp_size outside.
96 // Deal with flat model.
97 if (total_bits <= MMB_FLAT_MAX_BITS) {
98 memcpy(comp, bits, comp_size);
99 return 1;
100 }
101 // Deal with all cleared mmb.
102 if (mmb_load(bits) == 0) {
103 memcpy(comp, bits, sizeof(MMB_TYPE));
104 return 1;
105 }
106 // Deal with normal pyramid mmb.
107 const u32 max_level = mmbit_maxlevel(total_bits);
108 u32 level = 0;
109 u32 key = 0;
110 u32 key_rem = 0;
111 // Iteration-version of DFS
112 while (1) {
113 if (key_rem < MMB_KEY_BITS) {
114 const u8 *block_ptr = mmbit_get_level_root_const(bits, level) +
115 key * sizeof(MMB_TYPE);
116 MMB_TYPE block = mmb_load(block_ptr);
117 MMB_TYPE block_1 = block & ~mmb_mask_zero_to_nocheck(key_rem);
118 if (mmb_popcount(block) == mmb_popcount(block_1)) {
119 memcpy(comp, &block, sizeof(MMB_TYPE));
120 comp += sizeof(MMB_TYPE);
121 }
122 if (level < max_level && block_1) {
123 key = (key << MMB_KEY_SHIFT) + mmb_ctz(block_1);
124 key_rem = 0;
125 level++;
126 continue;
127 }
128 }
129 if (level-- == 0) {
130 break;
131 }
132 key_rem = (key & MMB_KEY_MASK) + 1;
133 key >>= MMB_KEY_SHIFT;
134 }
135 assert((u32)(comp - comp_init) == comp_size);
136 return 1;
137}
138
139/** \brief decompress API. */
140static really_inline
141char mmbit_decompress(u8 *bits, u32 total_bits, const u8 *comp,
142 size_t *comp_space, size_t max_comp_space) {
143 UNUSED const u8 *comp_init = comp;
144 size_t comp_size;
145 // Deal with flat model.
146 if (total_bits <= MMB_FLAT_MAX_BITS) {
147 comp_size = ROUNDUP_N(total_bits, 8) / 8;
148 memcpy(bits, comp, comp_size);
149 *comp_space = comp_size;
150 return 1;
151 }
152 // Deal with all cleared mmb.
153 if (mmb_load(comp) == 0) {
154 comp_size = sizeof(MMB_TYPE);
155 memcpy(bits, comp, comp_size);
156 *comp_space = comp_size;
157 return 1;
158 }
159 // Deal with normal mmb.
160 u32 max_level = mmbit_maxlevel(total_bits);
161 u32 level = 0;
162 u32 key = 0;
163 u32 key_rem = 0;
164 UNUSED const u8 *comp_end = comp_init + max_comp_space;
165 // Iteration-version of DFS
166 memcpy(bits, comp, sizeof(MMB_TYPE)); // Copy root block first.
167 comp += sizeof(MMB_TYPE);
168 while (1) {
169 if (key_rem < MMB_KEY_BITS) {
170 u8 *block_ptr = mmbit_get_level_root(bits, level) +
171 key * sizeof(MMB_TYPE);
172 MMB_TYPE block = mmb_load(block_ptr);
173 MMB_TYPE block_1 = block & ~mmb_mask_zero_to_nocheck(key_rem);
174 if (level < max_level && block_1) {
175 key = (key << MMB_KEY_SHIFT) + mmb_ctz(block_1);
176 u8 *block_ptr_1 = mmbit_get_level_root(bits, level + 1) +
177 key * sizeof(MMB_TYPE);
178 memcpy(block_ptr_1, comp, sizeof(MMB_TYPE));
179 comp += sizeof(MMB_TYPE);
180 if (comp > comp_end) {
181 return 0; // Out of buffer.
182 }
183 key_rem = 0;
184 level++;
185 continue;
186 }
187 }
188 if (level-- == 0) {
189 break;
190 }
191 key_rem = (key & MMB_KEY_MASK) + 1;
192 key >>= MMB_KEY_SHIFT;
193 }
194 comp_size = (u32)(comp - comp_init);
195 *comp_space = comp_size;
196 return 1;
197}
198
199#ifdef __cplusplus
200} // extern "C"
201#endif
202
203#endif // MULTBIT_COMPRESS_H
204
205