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 */
41 void 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 */
131 void 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 */
238 void 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 */
308 void 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 
NULL
#define NULL
Definition: def.h:267
SCIPdecodeDualBit
void SCIPdecodeDualBit(const SCIP_DUALPACKET *inp, int *out, int count)
Definition: bitencode.c:308
SCIPencodeSingleBit
void SCIPencodeSingleBit(const int *inp, SCIP_SINGLEPACKET *out, int count)
Definition: bitencode.c:41
bitencode.h
packing single and dual bit values
SCIPdecodeSingleBit
void SCIPdecodeSingleBit(const SCIP_SINGLEPACKET *inp, int *out, int count)
Definition: bitencode.c:131
SCIPencodeDualBit
void SCIPencodeDualBit(const int *inp, SCIP_DUALPACKET *out, int count)
Definition: bitencode.c:238
SCIP_DUALPACKET
unsigned int SCIP_DUALPACKET
Definition: bitencode.h:42
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
def.h
common defines and data types used in all packages of SCIP