parallel-computing/bitcopy.c at main · bortoq/parallel-computing · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
/*
 * TODO: find author on stackoverflow and ask for license
 *
 * update 20241021:
 *  fixed warning: comparison of integer expressions of different signedness: ‘unsigned int’ and ‘int’
 */
#include <stdio.h>
#include <limits.h>
#include <string.h>
#include <stddef.h>

/*
 * copy bits from one array to another (n, src, s, dst, d)
 *
 * n - number of bits to copy
 * src - source array
 * s - source bit index
 * dst - destination array
 * d - destination bit index
 */
void bitcpy(size_t src_len, const void *src_org, size_t src_offset, void *dst_org, size_t dst_offset)
{
#define PREPARE_FIRST_COPY()                                  \
    do {                                                      \
      if ((signed)src_len >= (CHAR_BIT - dst_offset_modulo)) {\
        *dst &= reverse_mask[dst_offset_modulo];              \
        src_len -= CHAR_BIT - dst_offset_modulo;              \
      }                                                       \
      else {                                                  \
        *dst &= reverse_mask[dst_offset_modulo]               \
          | reverse_mask_xor[dst_offset_modulo + src_len];    \
        c &= reverse_mask[dst_offset_modulo + src_len];       \
        src_len = 0;                                          \
      }                                                       \
    } while(0)

  static const unsigned char reverse_mask[] = {
    0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff};
  static const unsigned char reverse_mask_xor[] = {
    0xff, 0x7f, 0x3f, 0x1f, 0x0f, 0x07, 0x03, 0x01, 0x00};

  if(src_len)
  {
    const unsigned char *src;
    unsigned char *dst;
    int src_offset_modulo;
    int dst_offset_modulo;

    src = (const unsigned char*)src_org + (src_offset / CHAR_BIT);
    dst = (unsigned char*)dst_org + (dst_offset / CHAR_BIT);

    src_offset_modulo = src_offset % CHAR_BIT;
    dst_offset_modulo = dst_offset % CHAR_BIT;

    if(src_offset_modulo == dst_offset_modulo)
    {
      int byte_len;
      int src_len_modulo;
      if(src_offset_modulo)
      {
        unsigned char c;

        c = reverse_mask_xor[dst_offset_modulo] & *src++;
        PREPARE_FIRST_COPY();
        *dst++ |= c;
      }

      byte_len = src_len / CHAR_BIT;
      src_len_modulo = src_len % CHAR_BIT;

      if(byte_len)
      {
        memcpy(dst, src, byte_len);
        src += byte_len;
        dst += byte_len;
      }
      if(src_len_modulo)
      {
        *dst &= reverse_mask_xor[src_len_modulo];
        *dst |= reverse_mask[src_len_modulo] & *src;
      }
    }
    else
    {
      int bit_diff_ls;
      int bit_diff_rs;
      int byte_len;
      int src_len_modulo;
      unsigned char c;

      /* Begin: Line things up on destination */
      if(src_offset_modulo > dst_offset_modulo)
      {
        bit_diff_ls = src_offset_modulo - dst_offset_modulo;
        bit_diff_rs = CHAR_BIT - bit_diff_ls;

        c = *src++ << bit_diff_ls;
        c |= *src >> bit_diff_rs;
        c &= reverse_mask_xor[dst_offset_modulo];
      }
      else
      {
        bit_diff_rs = dst_offset_modulo - src_offset_modulo;
        bit_diff_ls = CHAR_BIT - bit_diff_rs;

        c = *src >> bit_diff_rs & reverse_mask_xor[dst_offset_modulo];
      }

      PREPARE_FIRST_COPY();
      *dst++ |= c;

      /* Middle: copy with only shifting the source */
      byte_len = src_len / CHAR_BIT;

      while(--byte_len >= 0)
      {
        c = *src++ << bit_diff_ls;
        c |= *src >> bit_diff_rs;
        *dst++ = c;
      }

      /* End: copy the remaining bits */
      src_len_modulo = src_len % CHAR_BIT;
      if(src_len_modulo)
      {
        c = *src++ << bit_diff_ls;
        c |= *src >> bit_diff_rs;
        c &= reverse_mask[src_len_modulo];

        *dst &= reverse_mask_xor[src_len_modulo];
        *dst |= c;
      }
    }
  }
}