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