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