1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 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  	
382