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-2025 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 */
    41void 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 */
    131void 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 */
    238void 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 */
    308void 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
    SCIPdecodeDualBit
    void SCIPdecodeDualBit(const SCIP_DUALPACKET *inp, int *out, int count)
    Definition: bitencode.c:308
    SCIPencodeDualBit
    void SCIPencodeDualBit(const int *inp, SCIP_DUALPACKET *out, int count)
    Definition: bitencode.c:238
    SCIPencodeSingleBit
    void SCIPencodeSingleBit(const int *inp, SCIP_SINGLEPACKET *out, int count)
    Definition: bitencode.c:41
    SCIPdecodeSingleBit
    void SCIPdecodeSingleBit(const SCIP_SINGLEPACKET *inp, int *out, int count)
    Definition: bitencode.c:131
    bitencode.h
    packing single and dual bit values
    SCIP_SINGLEPACKETSIZE
    #define SCIP_SINGLEPACKETSIZE
    Definition: bitencode.h:41
    SCIP_DUALPACKETSIZE
    #define SCIP_DUALPACKETSIZE
    Definition: bitencode.h:43
    SCIP_SINGLEPACKET
    unsigned int SCIP_SINGLEPACKET
    Definition: bitencode.h:40
    SCIP_DUALPACKET
    unsigned int SCIP_DUALPACKET
    Definition: bitencode.h:42
    def.h
    common defines and data types used in all packages of SCIP
    NULL
    #define NULL
    Definition: def.h:248