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