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-2019 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 rest;
72  int nfull;
73  const int packetsize = (int) SCIP_SINGLEPACKETSIZE;
74 
75  assert(inp != NULL || count == 0);
76  assert(out != NULL || count == 0);
77  assert(count >= 0);
78  assert(packetsize == 32);
79 
80  rest = count % packetsize;
81  nfull = count - rest;
82 
83  for( int i = 0; i < nfull; i += packetsize )
84  {
85  assert(inp != NULL);
86  assert(out != NULL);
87 
88 #ifndef NDEBUG
89  {
90  for( int j = 0; j < packetsize; ++j )
91  assert(0 <= inp[j] && inp[j] <= 1);
92  }
93 #endif
94  *out++ =
95  mask[0][inp[0]] | mask[1][inp[1]] | mask[2][inp[2]] | mask[3][inp[3]]
96  | mask[4][inp[4]] | mask[5][inp[5]] | mask[6][inp[6]] | mask[7][inp[7]]
97  | mask[8][inp[8]] | mask[9][inp[9]] | mask[10][inp[10]] | mask[11][inp[11]]
98  | mask[12][inp[12]] | mask[13][inp[13]] | mask[14][inp[14]] | mask[15][inp[15]]
99  | mask[16][inp[16]] | mask[17][inp[17]] | mask[18][inp[18]] | mask[19][inp[19]]
100  | mask[20][inp[20]] | mask[21][inp[21]] | mask[22][inp[22]] | mask[23][inp[23]]
101  | mask[24][inp[24]] | mask[25][inp[25]] | mask[26][inp[26]] | mask[27][inp[27]]
102  | mask[28][inp[28]] | mask[29][inp[29]] | mask[30][inp[30]] | mask[31][inp[31]];
103  inp += packetsize;
104  }
105 
106  if( rest > 0 )
107  {
108  SCIP_SINGLEPACKET m = (SCIP_SINGLEPACKET) 0u;
109 
110  assert(inp != NULL);
111  assert(out != NULL);
112 
113  for( int i = 0; i < rest; i++ )
114  m |= mask[i][inp[i]];
115  *out = m;
116  }
117 }
118 
119 /** decode a packed single bit vector into unpacked format */
120 void SCIPdecodeSingleBit(
121  const SCIP_SINGLEPACKET* inp, /**< packed input vector */
122  int* out, /**< buffer to store unpacked vector */
123  int count /**< number of elements */
124  )
125 {
126  SCIP_SINGLEPACKET m;
127  int rest;
128  int nfull;
129  int i;
130 
131  assert(inp != NULL || count == 0);
132  assert(out != NULL || count == 0);
133  assert(count >= 0);
134  assert(SCIP_SINGLEPACKETSIZE == 32);
135 
136  rest = count % (int)SCIP_SINGLEPACKETSIZE;
137  nfull = count - rest;
138 
139  for( i = 0; i < nfull; i += (int)SCIP_SINGLEPACKETSIZE )
140  {
141  assert(inp != NULL);
142  assert(out != NULL);
143 
144  m = *inp++;
145 
146  *out++ = m & 1;
147  m >>= 1;
148  *out++ = m & 1;
149  m >>= 1;
150  *out++ = m & 1;
151  m >>= 1;
152  *out++ = m & 1;
153  m >>= 1;
154  *out++ = m & 1;
155  m >>= 1;
156  *out++ = m & 1;
157  m >>= 1;
158  *out++ = m & 1;
159  m >>= 1;
160  *out++ = m & 1;
161  m >>= 1;
162  *out++ = m & 1;
163  m >>= 1;
164  *out++ = m & 1;
165  m >>= 1;
166  *out++ = m & 1;
167  m >>= 1;
168  *out++ = m & 1;
169  m >>= 1;
170  *out++ = m & 1;
171  m >>= 1;
172  *out++ = m & 1;
173  m >>= 1;
174  *out++ = m & 1;
175  m >>= 1;
176  *out++ = m & 1;
177  m >>= 1;
178  *out++ = m & 1;
179  m >>= 1;
180  *out++ = m & 1;
181  m >>= 1;
182  *out++ = m & 1;
183  m >>= 1;
184  *out++ = m & 1;
185  m >>= 1;
186  *out++ = m & 1;
187  m >>= 1;
188  *out++ = m & 1;
189  m >>= 1;
190  *out++ = m & 1;
191  m >>= 1;
192  *out++ = m & 1;
193  m >>= 1;
194  *out++ = m & 1;
195  m >>= 1;
196  *out++ = m & 1;
197  m >>= 1;
198  *out++ = m & 1;
199  m >>= 1;
200  *out++ = m & 1;
201  m >>= 1;
202  *out++ = m & 1;
203  m >>= 1;
204  *out++ = m & 1;
205  m >>= 1;
206  *out++ = m & 1;
207  m >>= 1;
208  *out++ = m & 1;
209  assert(m >> 1 == 0);
210  }
211 
212  if( rest > 0 )
213  {
214  assert(inp != NULL);
215  assert(out != NULL);
216 
217  m = *inp;
218  for( i = 0; i < rest; i++ )
219  {
220  *out++ = m & 1;
221  m >>= 1;
222  }
223  }
224 }
225 
226 /** encode a dual bit vector into packed format */
227 void SCIPencodeDualBit(
228  const int* inp, /**< unpacked input vector */
229  SCIP_DUALPACKET* out, /**< buffer to store the packed vector */
230  int count /**< number of elements */
231  )
232 {
233  static const SCIP_DUALPACKET mask[SCIP_DUALPACKETSIZE][4] = { /* if the packet size changes, the mask has to be updated */
234  {0x00000000, 0x00000001, 0x00000002, 0x00000003},
235  {0x00000000, 0x00000004, 0x00000008, 0x0000000C},
236  {0x00000000, 0x00000010, 0x00000020, 0x00000030},
237  {0x00000000, 0x00000040, 0x00000080, 0x000000C0},
238  {0x00000000, 0x00000100, 0x00000200, 0x00000300},
239  {0x00000000, 0x00000400, 0x00000800, 0x00000C00},
240  {0x00000000, 0x00001000, 0x00002000, 0x00003000},
241  {0x00000000, 0x00004000, 0x00008000, 0x0000C000},
242  {0x00000000, 0x00010000, 0x00020000, 0x00030000},
243  {0x00000000, 0x00040000, 0x00080000, 0x000C0000},
244  {0x00000000, 0x00100000, 0x00200000, 0x00300000},
245  {0x00000000, 0x00400000, 0x00800000, 0x00C00000},
246  {0x00000000, 0x01000000, 0x02000000, 0x03000000},
247  {0x00000000, 0x04000000, 0x08000000, 0x0C000000},
248  {0x00000000, 0x10000000, 0x20000000, 0x30000000},
249  {0x00000000, 0x40000000, 0x80000000, 0xC0000000}
250  };
251  int rest;
252  int nfull;
253  const int dualpacketsize = (int) SCIP_DUALPACKETSIZE;
254 
255  assert(inp != NULL || count == 0);
256  assert(out != NULL || count == 0);
257  assert(count >= 0);
258  assert(dualpacketsize == 16);
259 
260  rest = count % dualpacketsize;
261  nfull = count - rest;
262 
263  for( int i = 0; i < nfull; i += dualpacketsize, inp += dualpacketsize )
264  {
265  assert(inp != NULL);
266  assert(out != NULL);
267 
268 #ifndef NDEBUG
269  {
270  for( int j = 0; j < dualpacketsize; ++j )
271  assert(0 <= inp[j] && inp[j] <= 3);
272  }
273 #endif
274  *out++ =
275  mask[0][inp[0]] | mask[1][inp[1]] | mask[2][inp[2]] | mask[3][inp[3]]
276  | mask[4][inp[4]] | mask[5][inp[5]] | mask[6][inp[6]]
277  | mask[7][inp[7]] | mask[8][inp[8]] | mask[9][inp[9]]
278  | mask[10][inp[10]] | mask[11][inp[11]] | mask[12][inp[12]]
279  | mask[13][inp[13]] | mask[14][inp[14]] | mask[15][inp[15]];
280  }
281 
282  if( rest > 0 )
283  {
284  SCIP_DUALPACKET m = (SCIP_DUALPACKET) 0u;
285 
286  assert(inp != NULL);
287  assert(out != NULL);
288 
289  for( int i = 0; i < rest; i++ )
290  m |= mask[i][inp[i]];
291  *out = m;
292  }
293 }
294 
295 /** decode a packed dual bit vector into unpacked format */
296 void SCIPdecodeDualBit(
297  const SCIP_DUALPACKET* inp, /**< packed input vector */
298  int* out, /**< buffer to store unpacked vector */
299  int count /**< number of elements */
300  )
301 {
302  SCIP_DUALPACKET m;
303  int rest;
304  int nfull;
305  int i;
306 
307  assert(inp != NULL || count == 0);
308  assert(out != NULL || count == 0);
309  assert(count >= 0);
310  assert(SCIP_DUALPACKETSIZE == 16);
311 
312  rest = count % (int)SCIP_DUALPACKETSIZE;
313  nfull = count - rest;
314 
315  for( i = 0; i < nfull; i += (int)SCIP_DUALPACKETSIZE )
316  {
317  assert(inp != NULL);
318  assert(out != NULL);
319 
320  m = *inp++;
321 
322  *out++ = m & 3;
323  m >>= 2;
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  assert(m >> 2 == 0);
354  }
355 
356  if( rest > 0 )
357  {
358  assert(inp != NULL);
359  assert(out != NULL);
360 
361  m = *inp;
362  for( i = 0; i < rest; i++ )
363  {
364  *out++ = m & 3;
365  m >>= 2;
366  }
367  }
368 }
369 
NULL
#define NULL
Definition: def.h:246
SCIPdecodeDualBit
void SCIPdecodeDualBit(const SCIP_DUALPACKET *inp, int *out, int count)
Definition: bitencode.c:296
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:120
SCIPencodeDualBit
void SCIPencodeDualBit(const int *inp, SCIP_DUALPACKET *out, int count)
Definition: bitencode.c:227
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