Scippy

SCIP

Solving Constraint Integer Programs

bitencode.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file bitencode.c
26 * @ingroup OTHER_CFILES
27 * @brief packing single and dual bit values
28 * @author Thorsten Koch
29 * @author Tobias Achterberg
30 */
31
32/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33
34#include <assert.h>
35
36#include "scip/def.h"
37#include "scip/bitencode.h"
38
39
40/** encode a single bit vector into packed format */
41void SCIPencodeSingleBit(
42 const int* inp, /**< unpacked input vector */
43 SCIP_SINGLEPACKET* out, /**< buffer to store the packed vector */
44 int count /**< number of elements */
45 )
46{
47 static const SCIP_SINGLEPACKET mask[SCIP_SINGLEPACKETSIZE][2] = { /* if the packet size changes, the mask has to be updated */
48 {0x00000000, 0x00000001},
49 {0x00000000, 0x00000002},
50 {0x00000000, 0x00000004},
51 {0x00000000, 0x00000008},
52 {0x00000000, 0x00000010},
53 {0x00000000, 0x00000020},
54 {0x00000000, 0x00000040},
55 {0x00000000, 0x00000080},
56 {0x00000000, 0x00000100},
57 {0x00000000, 0x00000200},
58 {0x00000000, 0x00000400},
59 {0x00000000, 0x00000800},
60 {0x00000000, 0x00001000},
61 {0x00000000, 0x00002000},
62 {0x00000000, 0x00004000},
63 {0x00000000, 0x00008000},
64 {0x00000000, 0x00010000},
65 {0x00000000, 0x00020000},
66 {0x00000000, 0x00040000},
67 {0x00000000, 0x00080000},
68 {0x00000000, 0x00100000},
69 {0x00000000, 0x00200000},
70 {0x00000000, 0x00400000},
71 {0x00000000, 0x00800000},
72 {0x00000000, 0x01000000},
73 {0x00000000, 0x02000000},
74 {0x00000000, 0x04000000},
75 {0x00000000, 0x08000000},
76 {0x00000000, 0x10000000},
77 {0x00000000, 0x20000000},
78 {0x00000000, 0x40000000},
79 {0x00000000, 0x80000000}
80 };
81 int rest;
82 int nfull;
83 const int packetsize = (int) SCIP_SINGLEPACKETSIZE;
84
85 assert(inp != NULL || count == 0);
86 assert(out != NULL || count == 0);
87 assert(count >= 0);
88 assert(packetsize == 32);
89
90 rest = count % packetsize;
91 nfull = count - rest;
92
93 for( int i = 0; i < nfull; i += packetsize )
94 {
95 assert(inp != NULL);
96 assert(out != NULL);
97
98#ifndef NDEBUG
99 {
100 for( int j = 0; j < packetsize; ++j )
101 assert(0 <= inp[j] && inp[j] <= 1);
102 }
103#endif
104 *out++ =
105 mask[0][inp[0]] | mask[1][inp[1]] | mask[2][inp[2]] | mask[3][inp[3]]
106 | mask[4][inp[4]] | mask[5][inp[5]] | mask[6][inp[6]] | mask[7][inp[7]]
107 | mask[8][inp[8]] | mask[9][inp[9]] | mask[10][inp[10]] | mask[11][inp[11]]
108 | mask[12][inp[12]] | mask[13][inp[13]] | mask[14][inp[14]] | mask[15][inp[15]]
109 | mask[16][inp[16]] | mask[17][inp[17]] | mask[18][inp[18]] | mask[19][inp[19]]
110 | mask[20][inp[20]] | mask[21][inp[21]] | mask[22][inp[22]] | mask[23][inp[23]]
111 | mask[24][inp[24]] | mask[25][inp[25]] | mask[26][inp[26]] | mask[27][inp[27]]
112 | mask[28][inp[28]] | mask[29][inp[29]] | mask[30][inp[30]] | mask[31][inp[31]];
113 inp += packetsize;
114 }
115
116 if( rest > 0 )
117 {
118 SCIP_SINGLEPACKET m = (SCIP_SINGLEPACKET) 0u;
119
120 assert(inp != NULL);
121 assert(out != NULL);
122 assert(rest <= (int) SCIP_SINGLEPACKETSIZE);
123
124 for( int i = 0; i < rest; i++ )
125 m |= mask[i][inp[i]];
126 *out = m;
127 }
128}
129
130/** decode a packed single bit vector into unpacked format */
131void SCIPdecodeSingleBit(
132 const SCIP_SINGLEPACKET* inp, /**< packed input vector */
133 int* out, /**< buffer to store unpacked vector */
134 int count /**< number of elements */
135 )
136{
137 SCIP_SINGLEPACKET m;
138 int rest;
139 int nfull;
140 int i;
141
142 assert(inp != NULL || count == 0);
143 assert(out != NULL || count == 0);
144 assert(count >= 0);
145 assert(SCIP_SINGLEPACKETSIZE == 32); /*lint !e506*/
146
147 rest = count % (int)SCIP_SINGLEPACKETSIZE;
148 nfull = count - rest;
149
150 for( i = 0; i < nfull; i += (int)SCIP_SINGLEPACKETSIZE )
151 {
152 assert(inp != NULL);
153 assert(out != NULL);
154
155 m = *inp++;
156
157 *out++ = (int)m & 1;
158 m >>= 1;
159 *out++ = (int)m & 1;
160 m >>= 1;
161 *out++ = (int)m & 1;
162 m >>= 1;
163 *out++ = (int)m & 1;
164 m >>= 1;
165 *out++ = (int)m & 1;
166 m >>= 1;
167 *out++ = (int)m & 1;
168 m >>= 1;
169 *out++ = (int)m & 1;
170 m >>= 1;
171 *out++ = (int)m & 1;
172 m >>= 1;
173 *out++ = (int)m & 1;
174 m >>= 1;
175 *out++ = (int)m & 1;
176 m >>= 1;
177 *out++ = (int)m & 1;
178 m >>= 1;
179 *out++ = (int)m & 1;
180 m >>= 1;
181 *out++ = (int)m & 1;
182 m >>= 1;
183 *out++ = (int)m & 1;
184 m >>= 1;
185 *out++ = (int)m & 1;
186 m >>= 1;
187 *out++ = (int)m & 1;
188 m >>= 1;
189 *out++ = (int)m & 1;
190 m >>= 1;
191 *out++ = (int)m & 1;
192 m >>= 1;
193 *out++ = (int)m & 1;
194 m >>= 1;
195 *out++ = (int)m & 1;
196 m >>= 1;
197 *out++ = (int)m & 1;
198 m >>= 1;
199 *out++ = (int)m & 1;
200 m >>= 1;
201 *out++ = (int)m & 1;
202 m >>= 1;
203 *out++ = (int)m & 1;
204 m >>= 1;
205 *out++ = (int)m & 1;
206 m >>= 1;
207 *out++ = (int)m & 1;
208 m >>= 1;
209 *out++ = (int)m & 1;
210 m >>= 1;
211 *out++ = (int)m & 1;
212 m >>= 1;
213 *out++ = (int)m & 1;
214 m >>= 1;
215 *out++ = (int)m & 1;
216 m >>= 1;
217 *out++ = (int)m & 1;
218 m >>= 1;
219 *out++ = (int)m & 1;
220 assert(m >> 1 == 0);
221 }
222
223 if( rest > 0 )
224 {
225 assert(inp != NULL);
226 assert(out != NULL);
227
228 m = *inp;
229 for( i = 0; i < rest; i++ )
230 {
231 *out++ = (int)m & 1;
232 m >>= 1;
233 }
234 }
235}
236
237/** encode a dual bit vector into packed format */
238void SCIPencodeDualBit(
239 const int* inp, /**< unpacked input vector */
240 SCIP_DUALPACKET* out, /**< buffer to store the packed vector */
241 int count /**< number of elements */
242 )
243{
244 static const SCIP_DUALPACKET mask[SCIP_DUALPACKETSIZE][4] = { /* if the packet size changes, the mask has to be updated */
245 {0x00000000, 0x00000001, 0x00000002, 0x00000003},
246 {0x00000000, 0x00000004, 0x00000008, 0x0000000C},
247 {0x00000000, 0x00000010, 0x00000020, 0x00000030},
248 {0x00000000, 0x00000040, 0x00000080, 0x000000C0},
249 {0x00000000, 0x00000100, 0x00000200, 0x00000300},
250 {0x00000000, 0x00000400, 0x00000800, 0x00000C00},
251 {0x00000000, 0x00001000, 0x00002000, 0x00003000},
252 {0x00000000, 0x00004000, 0x00008000, 0x0000C000},
253 {0x00000000, 0x00010000, 0x00020000, 0x00030000},
254 {0x00000000, 0x00040000, 0x00080000, 0x000C0000},
255 {0x00000000, 0x00100000, 0x00200000, 0x00300000},
256 {0x00000000, 0x00400000, 0x00800000, 0x00C00000},
257 {0x00000000, 0x01000000, 0x02000000, 0x03000000},
258 {0x00000000, 0x04000000, 0x08000000, 0x0C000000},
259 {0x00000000, 0x10000000, 0x20000000, 0x30000000},
260 {0x00000000, 0x40000000, 0x80000000, 0xC0000000}
261 };
262 int rest;
263 int nfull;
264 const int dualpacketsize = (int) SCIP_DUALPACKETSIZE;
265
266 assert(inp != NULL || count == 0);
267 assert(out != NULL || count == 0);
268 assert(count >= 0);
269 assert(dualpacketsize == 16);
270
271 rest = count % dualpacketsize;
272 nfull = count - rest;
273
274 for( int i = 0; i < nfull; i += dualpacketsize, inp += dualpacketsize ) /*lint !e679*/
275 {
276 assert(inp != NULL);
277 assert(out != NULL);
278
279#ifndef NDEBUG
280 {
281 for( int j = 0; j < dualpacketsize; ++j )
282 assert(0 <= inp[j] && inp[j] <= 3);
283 }
284#endif
285 *out++ =
286 mask[0][inp[0]] | mask[1][inp[1]] | mask[2][inp[2]] | mask[3][inp[3]]
287 | mask[4][inp[4]] | mask[5][inp[5]] | mask[6][inp[6]]
288 | mask[7][inp[7]] | mask[8][inp[8]] | mask[9][inp[9]]
289 | mask[10][inp[10]] | mask[11][inp[11]] | mask[12][inp[12]]
290 | mask[13][inp[13]] | mask[14][inp[14]] | mask[15][inp[15]];
291 }
292
293 if( rest > 0 )
294 {
295 SCIP_DUALPACKET m = (SCIP_DUALPACKET) 0u;
296
297 assert(inp != NULL);
298 assert(out != NULL);
299 assert(rest <= (int) SCIP_DUALPACKETSIZE);
300
301 for( int i = 0; i < rest; i++ )
302 m |= mask[i][inp[i]];
303 *out = m;
304 }
305}
306
307/** decode a packed dual bit vector into unpacked format */
308void SCIPdecodeDualBit(
309 const SCIP_DUALPACKET* inp, /**< packed input vector */
310 int* out, /**< buffer to store unpacked vector */
311 int count /**< number of elements */
312 )
313{
314 SCIP_DUALPACKET m;
315 int rest;
316 int nfull;
317 int i;
318
319 assert(inp != NULL || count == 0);
320 assert(out != NULL || count == 0);
321 assert(count >= 0);
322 assert(SCIP_DUALPACKETSIZE == 16); /*lint !e506*/
323
324 rest = count % (int)SCIP_DUALPACKETSIZE;
325 nfull = count - rest;
326
327 for( i = 0; i < nfull; i += (int)SCIP_DUALPACKETSIZE )
328 {
329 assert(inp != NULL);
330 assert(out != NULL);
331
332 m = *inp++;
333
334 *out++ = (int)m & 3;
335 m >>= 2;
336 *out++ = (int)m & 3;
337 m >>= 2;
338 *out++ = (int)m & 3;
339 m >>= 2;
340 *out++ = (int)m & 3;
341 m >>= 2;
342 *out++ = (int)m & 3;
343 m >>= 2;
344 *out++ = (int)m & 3;
345 m >>= 2;
346 *out++ = (int)m & 3;
347 m >>= 2;
348 *out++ = (int)m & 3;
349 m >>= 2;
350 *out++ = (int)m & 3;
351 m >>= 2;
352 *out++ = (int)m & 3;
353 m >>= 2;
354 *out++ = (int)m & 3;
355 m >>= 2;
356 *out++ = (int)m & 3;
357 m >>= 2;
358 *out++ = (int)m & 3;
359 m >>= 2;
360 *out++ = (int)m & 3;
361 m >>= 2;
362 *out++ = (int)m & 3;
363 m >>= 2;
364 *out++ = (int)m & 3;
365 assert(m >> 2 == 0);
366 }
367
368 if( rest > 0 )
369 {
370 assert(inp != NULL);
371 assert(out != NULL);
372
373 m = *inp;
374 for( i = 0; i < rest; i++ )
375 {
376 *out++ = (int)m & 3;
377 m >>= 2;
378 }
379 }
380}
381
SCIPdecodeDualBit
void SCIPdecodeDualBit(const SCIP_DUALPACKET *inp, int *out, int count)
Definition: bitencode.c:308
SCIPencodeDualBit
void SCIPencodeDualBit(const int *inp, SCIP_DUALPACKET *out, int count)
Definition: bitencode.c:238
SCIPencodeSingleBit
void SCIPencodeSingleBit(const int *inp, SCIP_SINGLEPACKET *out, int count)
Definition: bitencode.c:41
SCIPdecodeSingleBit
void SCIPdecodeSingleBit(const SCIP_SINGLEPACKET *inp, int *out, int count)
Definition: bitencode.c:131
bitencode.h
packing single and dual bit values
SCIP_SINGLEPACKETSIZE
#define SCIP_SINGLEPACKETSIZE
Definition: bitencode.h:41
SCIP_DUALPACKETSIZE
#define SCIP_DUALPACKETSIZE
Definition: bitencode.h:43
SCIP_SINGLEPACKET
unsigned int SCIP_SINGLEPACKET
Definition: bitencode.h:40
SCIP_DUALPACKET
unsigned int SCIP_DUALPACKET
Definition: bitencode.h:42
def.h
common defines and data types used in all packages of SCIP
NULL
#define NULL
Definition: def.h:267