BitString::bitOr()   A
last analyzed

Complexity

Conditions 5
Paths 4

Size

Total Lines 14
Code Lines 7

Duplication

Lines 0
Ratio 0 %

Importance

Changes 0
Metric Value
cc 5
eloc 7
nc 4
nop 1
dl 0
loc 14
rs 9.6111
c 0
b 0
f 0
1
<?php
2
declare(strict_types=1);
3
namespace Ivory\Value;
4
5
use Ivory\Exception\ImmutableException;
6
use Ivory\Exception\IncomparableException;
7
use Ivory\Exception\UndefinedOperationException;
8
use Ivory\Value\Alg\IComparable;
9
10
/**
11
 * A common super type for bit string types - strings of 1's and 0's.
12
 *
13
 * The objects are immutable, i.e., operations always produce a new object.
14
 * The representation and operations resemble the specification for bit string types in PostgreSQL.
15
 *
16
 * It is possible to access individual bits using the array indices (readonly). The leftmost bit is at offset 0. Testing
17
 * whether the bit string has a bit at a given offset may be performed using `isset($this[$offset])`. Note that, apart
18
 * from reading out of such a call, it does not test whether the given bit is *set* (i.e., whether it is 1) - it merely
19
 * tests whether it is legal to access it. Negative offsets may be used to get bits off the end of the string.
20
 *
21
 * @see https://www.postgresql.org/docs/11/datatype-bit.html PostgreSQL Bit String Types
22
 * @see https://www.postgresql.org/docs/11/functions-bitstring.html PostgreSQL Bit String Functions and Operators
23
 *
24
 * @todo optimize the internal representation (unpack('c*', $value) might be handy for constructing from string)
25
 */
26
abstract class BitString implements IComparable, \ArrayAccess
27
{
28
    protected $bits;
29
    protected $len;
30
31
32
    /**
33
     * @param string $bits
34
     */
35
    protected function __construct(string $bits)
36
    {
37
        if (!preg_match('~^[01]*$~', $bits)) {
38
            throw new \InvalidArgumentException('bits');
39
        }
40
41
        $this->bits = $bits;
42
        $this->len = strlen($bits);
43
    }
44
45
46
    /**
47
     * @return string textual representation of this bit string (index 0 is the leftmost bit): a string of 1's and 0's
48
     */
49
    public function toString(): string
50
    {
51
        return $this->bits;
52
    }
53
54
    /**
55
     * @return int number of bits in the bit string
56
     */
57
    public function getLength(): int
58
    {
59
        return $this->len;
60
    }
61
62
    /**
63
     * @return bool whether all the bits are zero
64
     */
65
    public function isZero(): bool
66
    {
67
        return !$this->isNonZero();
68
    }
69
70
    /**
71
     * @return bool whether some bit is one
72
     */
73
    public function isNonZero(): bool
74
    {
75
        for ($i = 0; $i < $this->len; $i++) {
76
            if ($this->bits[$i] == '1') {
77
                return true;
78
            }
79
        }
80
81
        return false;
82
    }
83
84
    /**
85
     * @param BitString|null $other
86
     * @return bool whether this and the other bit string are of the same type, have the same bits and same length
87
     */
88
    public function equals($other): bool
89
    {
90
        return (
91
            $other !== null &&
92
            get_class($this) == get_class($other) &&
93
            $this->bits == $other->bits
94
        );
95
    }
96
97
    public function compareTo($other): int
98
    {
99
        if ($other === null) {
100
            throw new \InvalidArgumentException('comparing with null');
101
        }
102
        if (get_class($this) != get_class($other)) {
103
            throw new IncomparableException();
104
        }
105
106
        return strcmp($this->bits, $other->bits);
107
    }
108
109
    /**
110
     * @param BitString $other any bit string of any length
111
     * @return bool whether this and the other bit string have the same bits, i.e., are the same 1's and 0's strings
112
     */
113
    public function bitEquals(BitString $other): bool
114
    {
115
        return ($this->bits === $other->bits); // ===: PHP would otherwise convert both strings to integers
116
    }
117
118
    /**
119
     * Finds out whether the operands intersect at a 1 bit.
120
     *
121
     * Works for any lengths of the bit strings. The shorter bit string is right-padded with 0's.
122
     *
123
     * @param BitString $other any bit string of any length
124
     * @return bool whether this and the other bit string share at least one set bit at the same offset
125
     */
126
    public function intersects(BitString $other): bool
127
    {
128
        for ($i = min($this->len, $other->len) - 1; $i >= 0; $i--) {
129
            if ($this->bits[$i] == '1' && $other->bits[$i] == '1') {
130
                return true;
131
            }
132
        }
133
134
        return false;
135
    }
136
137
    /**
138
     * Extracts a bit substring from this bit string.
139
     *
140
     * Note the semantics are according to the SQL standard, which PostgreSQL implements. That is, the arguments do NOT
141
     * work the same as for PHP {@link substr()} function.
142
     *
143
     * Examples:
144
     * - `substring(2)` on `'1101001'` yields `'101001'`
145
     * - `substring(2, 4)` on `'1101001'` yields `'1010'`
146
     * - `substring(2, 0)` on `'1101001'` yields `''`
147
     * - `substring(-2, 4)` on `'1101001'` yields `'1'`
148
     *
149
     * @param int $from position to start at;
150
     *                  one-based - e.g., <tt>$from = 2</tt> omits the first character;
151
     *                  if less than one, it yields the start of the string, but counting from the given (negative or
152
     *                    zero) position, effectively decreasing the <tt>$for</tt> argument, if given
153
     * @param int|null $for number of characters to take; must be non-negative;
154
     *                      <tt>null</tt> for the rest of the string
155
     * @return FixedBitString the substring of the bit string
156
     * @throws UndefinedOperationException when <tt>$for</tt> is negative
157
     */
158
    public function substring(int $from, ?int $for = null): FixedBitString
159
    {
160
        if ($for < 0) {
161
            throw new UndefinedOperationException('negative number of bits to take');
162
        }
163
164
        $offset = max(0, $from - 1);
165
        if ($offset >= $this->len) {
166
            return FixedBitString::fromString('');
167
        }
168
169
        if ($for === null) {
170
            $len = $this->len;
171
        } elseif ($from >= 0) {
172
            $len = $for;
173
        } else {
174
            $len = max(0, $for + $from - 1);
175
        }
176
177
        return FixedBitString::fromString(substr($this->bits, $offset, $len));
178
    }
179
180
    /**
181
     * Concatenates this bit string with another one.
182
     *
183
     * The result is a bit string with bits of this bit string followed by the bits from the `$concatenated` bit string.
184
     *
185
     * If both the operands are fixed-length of length `A` and `B`, the result is a fixed-length bit string of length
186
     * `A+B`. Otherwise, the result is a variable-length bit string.
187
     *
188
     * @param BitString $concatenated
189
     * @return VarBitString bit string made up by concatenating the <tt>$concatenated</tt> after this bit string
190
     */
191
    public function concat(BitString $concatenated): VarBitString
192
    {
193
        return VarBitString::fromString($this->bits . $concatenated->bits);
194
    }
195
196
    /**
197
     * Bitwise AND operation. Only legal for operands of equal bit lengths.
198
     *
199
     * @param BitString $other the other operand
200
     * @return FixedBitString new bit string: <tt>$this & $other</tt>
201
     * @throws UndefinedOperationException if the operands are of different bit lengths
202
     */
203
    public function bitAnd(BitString $other): FixedBitString
204
    {
205
        if ($this->len != $other->len) {
206
            throw new UndefinedOperationException('operands are of different bit lengths');
207
        }
208
209
        $res = str_repeat('0', $this->len);
210
        for ($i = 0; $i < $this->len; $i++) {
211
            if ($this->bits[$i] == '1' && $other->bits[$i] == '1') {
212
                $res[$i] = '1';
213
            }
214
        }
215
216
        return FixedBitString::fromString($res);
217
    }
218
219
    /**
220
     * Bitwise OR operation. Only legal for operands of equal bit lengths.
221
     *
222
     * @param BitString $other the other operand
223
     * @return FixedBitString new bit string: <tt>$this | $other</tt>
224
     * @throws UndefinedOperationException if the operands are of different bit lengths
225
     */
226
    public function bitOr(BitString $other): FixedBitString
227
    {
228
        if ($this->len != $other->len) {
229
            throw new UndefinedOperationException('operands are of different bit lengths');
230
        }
231
232
        $res = str_repeat('1', $this->len);
233
        for ($i = 0; $i < $this->len; $i++) {
234
            if ($this->bits[$i] == '0' && $other->bits[$i] == '0') {
235
                $res[$i] = '0';
236
            }
237
        }
238
239
        return FixedBitString::fromString($res);
240
    }
241
242
    /**
243
     * Bitwise exclusive OR operation. Only legal for operands of equal bit lengths.
244
     *
245
     * @param BitString $other the other operand
246
     * @return FixedBitString new bit string: <tt>$this ^ $other</tt>
247
     * @throws UndefinedOperationException if the operands are of different bit lengths
248
     */
249
    public function bitXor(BitString $other): FixedBitString
250
    {
251
        if ($this->len != $other->len) {
252
            throw new UndefinedOperationException('operands are of different bit lengths');
253
        }
254
255
        $res = str_repeat('0', $this->len);
256
        for ($i = 0; $i < $this->len; $i++) {
257
            if ($this->bits[$i] != $other->bits[$i]) {
258
                $res[$i] = '1';
259
            }
260
        }
261
262
        return FixedBitString::fromString($res);
263
    }
264
265
    /**
266
     * Bitwise negation, i.e., reverses all bits of the bit string.
267
     *
268
     * @return FixedBitString new bit string: <tt>~$this</tt>
269
     */
270
    public function bitNot(): FixedBitString
271
    {
272
        return FixedBitString::fromString(strtr($this->bits, '01', '10'));
273
    }
274
275
    /**
276
     * Shifts the bits to the left.
277
     *
278
     * The length of the bit string is preserved, thus, the `$shift` left trailing bits are discarded. The shifted bit
279
     * positions are filled with 0's.
280
     *
281
     * @param int $shift number of positions to shift the bits to the left;
282
     *                   might even be negative (results in shifting to the right by <tt>-$shift</tt>)
283
     * @return FixedBitString a bit string with bits shifted by <tt>$shift</tt> to the left
284
     */
285
    public function bitShiftLeft(int $shift): FixedBitString
286
    {
287
        if ($shift < 0) {
288
            return $this->bitShiftRight(-$shift);
289
        }
290
291
        $pad = min($this->len, $shift);
292
        $prefix = ($pad == $this->len ? '' : substr($this->bits, $pad));
293
        return FixedBitString::fromString($prefix . str_repeat('0', $pad));
294
    }
295
296
    /**
297
     * Shifts the bits to the right.
298
     *
299
     * The length of the bit string is preserved, thus, the `$shift` right trailing bits are discarded. The shifted bit
300
     * positions are filled with 0's.
301
     *
302
     * @param int $shift number of positions to shift the bits to the right;
303
     *                   might even be negative (results in shifting to the left by <tt>-$shift</tt>)
304
     * @return FixedBitString a bit string with bits shifted by <tt>$shift</tt> to the right
305
     */
306
    public function bitShiftRight(int $shift): FixedBitString
307
    {
308
        if ($shift < 0) {
309
            return $this->bitShiftLeft(-$shift);
310
        }
311
312
        $pad = min($this->len, $shift);
313
        $postfix = substr($this->bits, 0, $this->len - $pad);
314
        return FixedBitString::fromString(str_repeat('0', $pad) . $postfix);
315
    }
316
317
    /**
318
     * Rotates the bits to the left.
319
     *
320
     * @param int $rot the length of the rotation
321
     * @return FixedBitString a bit string with <tt>$rot</tt> (mod length) leftmost bits moved to the back of the bit
322
     *                          string
323
     */
324
    public function bitRotateLeft(int $rot): FixedBitString
325
    {
326
        if ($rot < 0) {
327
            return $this->bitRotateRight(-$rot);
328
        }
329
        if ($this->len == 0) {
330
            return FixedBitString::fromString('');
331
        }
332
333
        $pos = $rot % $this->len;
334
        return FixedBitString::fromString(substr($this->bits, $pos) . substr($this->bits, 0, $pos));
335
    }
336
337
    /**
338
     * Rotates the bits to the right.
339
     *
340
     * @param int $rot the length of the rotation
341
     * @return FixedBitString a bit string with <tt>$rot</tt> (mod length) rightmost bits moved to the front of the bit
342
     *                          string
343
     */
344
    public function bitRotateRight(int $rot): FixedBitString
345
    {
346
        if ($rot < 0) {
347
            return $this->bitRotateLeft(-$rot);
348
        }
349
        if ($this->len == 0) {
350
            return FixedBitString::fromString('');
351
        }
352
353
        $pos = $this->len - ($rot % $this->len);
354
        return FixedBitString::fromString(substr($this->bits, $pos) . substr($this->bits, 0, $pos));
355
    }
356
357
358
    public function __toString()
359
    {
360
        return $this->toString();
361
    }
362
363
364
    /**
365
     * @param int $offset the bit to know existence of; 0 for the leftmost bit, 1 for the next bit, -1 for the rightmost
366
     *                      bit, etc.
367
     * @return bool <tt>true</tt> if the bit string has <tt>$offset</tt>-th bit defined,
368
     *              <tt>false</tt> if the bit string is too short (i.e., shorter than <tt>$offset+1</tt> bits)
369
     */
370
    public function offsetExists($offset): bool
371
    {
372
        return isset($this->bits[$offset]);
373
    }
374
375
    /**
376
     * @param int $offset the bit to get; 0 for the leftmost bit, 1 for the next bit, -1 for the rightmost bit, etc.
377
     * @return int|null 0 or 1 depending on whether the <tt>$offset</tt>-th bit is set, or
378
     *                  <tt>null</tt> if outside of the bit string
379
     */
380
    public function offsetGet($offset): ?int
381
    {
382
        if (isset($this->bits[$offset])) {
383
            return (int)$this->bits[$offset];
384
        } else {
385
            return null;
386
        }
387
    }
388
389
    /**
390
     * Setting a bit is not implemented - the bit string is immutable.
391
     *
392
     * @param mixed $offset
393
     * @param mixed $value
394
     * @throws ImmutableException
395
     */
396
    public function offsetSet($offset, $value)
397
    {
398
        throw new ImmutableException();
399
    }
400
401
    /**
402
     * Unsetting a bit is not implemented - the bit string is immutable.
403
     *
404
     * @param mixed $offset
405
     * @throws ImmutableException
406
     */
407
    public function offsetUnset($offset)
408
    {
409
        throw new ImmutableException();
410
    }
411
}
412