1 /* 2 * Fast QR Code generator library 3 * 4 * Copyright (c) Project Nayuki. (MIT License) 5 * https://www.nayuki.io/page/fast-qr-code-generator-library 6 * 7 * Permission is hereby granted, free of charge, to any person obtaining a copy of 8 * this software and associated documentation files (the "Software"), to deal in 9 * the Software without restriction, including without limitation the rights to 10 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of 11 * the Software, and to permit persons to whom the Software is furnished to do so, 12 * subject to the following conditions: 13 * - The above copyright notice and this permission notice shall be included in 14 * all copies or substantial portions of the Software. 15 * - The Software is provided "as is", without warranty of any kind, express or 16 * implied, including but not limited to the warranties of merchantability, 17 * fitness for a particular purpose and noninfringement. In no event shall the 18 * authors or copyright holders be liable for any claim, damages or other 19 * liability, whether in an action of contract, tort or otherwise, arising from, 20 * out of or in connection with the Software or the use or other dealings in the 21 * Software. 22 */ 23 24 package io.nayuki.fastqrcodegen; 25 26 import java.util.Arrays; 27 import java.util.Objects; 28 29 30 // An appendable sequence of bits (0s and 1s), mainly used by QrSegment. 31 final class BitBuffer { 32 33 /*---- Fields ----*/ 34 35 int[] data; // In each 32-bit word, bits are filled from top down. 36 37 int bitLength; // Always non-negative. 38 39 40 41 /*---- Constructor ----*/ 42 43 // Creates an empty bit buffer. BitBuffer()44 public BitBuffer() { 45 data = new int[64]; 46 bitLength = 0; 47 } 48 49 50 51 /*---- Methods ----*/ 52 53 // Returns the bit at the given index, yielding 0 or 1. getBit(int index)54 public int getBit(int index) { 55 if (index < 0 || index >= bitLength) 56 throw new IndexOutOfBoundsException(); 57 return (data[index >>> 5] >>> ~index) & 1; 58 } 59 60 61 // Returns a new array representing this buffer's bits packed into 62 // bytes in big endian. The current bit length must be a multiple of 8. getBytes()63 public byte[] getBytes() { 64 if (bitLength % 8 != 0) 65 throw new IllegalStateException("Data is not a whole number of bytes"); 66 byte[] result = new byte[bitLength / 8]; 67 for (int i = 0; i < result.length; i++) 68 result[i] = (byte)(data[i >>> 2] >>> (~i << 3)); 69 return result; 70 } 71 72 73 // Appends the given number of low-order bits of the given value 74 // to this buffer. Requires 0 <= len <= 31 and 0 <= val < 2^len. appendBits(int val, int len)75 public void appendBits(int val, int len) { 76 if (len < 0 || len > 31 || val >>> len != 0) 77 throw new IllegalArgumentException("Value out of range"); 78 if (len > Integer.MAX_VALUE - bitLength) 79 throw new IllegalStateException("Maximum length reached"); 80 81 if (bitLength + len + 1 > data.length << 5) 82 data = Arrays.copyOf(data, data.length * 2); 83 assert bitLength + len <= data.length << 5; 84 85 int remain = 32 - (bitLength & 0x1F); 86 assert 1 <= remain && remain <= 32; 87 if (remain < len) { 88 data[bitLength >>> 5] |= val >>> (len - remain); 89 bitLength += remain; 90 assert (bitLength & 0x1F) == 0; 91 len -= remain; 92 val &= (1 << len) - 1; 93 remain = 32; 94 } 95 data[bitLength >>> 5] |= val << (remain - len); 96 bitLength += len; 97 } 98 99 100 // Appends to this buffer the sequence of bits represented by the given 101 // word array and given bit length. Requires 0 <= len <= 32 * vals.length. appendBits(int[] vals, int len)102 public void appendBits(int[] vals, int len) { 103 Objects.requireNonNull(vals); 104 if (len == 0) 105 return; 106 if (len < 0 || len > vals.length * 32L) 107 throw new IllegalArgumentException("Value out of range"); 108 int wholeWords = len / 32; 109 int tailBits = len % 32; 110 if (tailBits > 0 && vals[wholeWords] << tailBits != 0) 111 throw new IllegalArgumentException("Last word must have low bits clear"); 112 if (len > Integer.MAX_VALUE - bitLength) 113 throw new IllegalStateException("Maximum length reached"); 114 115 while (bitLength + len > data.length * 32) 116 data = Arrays.copyOf(data, data.length * 2); 117 118 int shift = bitLength % 32; 119 if (shift == 0) { 120 System.arraycopy(vals, 0, data, bitLength / 32, (len + 31) / 32); 121 bitLength += len; 122 } else { 123 for (int i = 0; i < wholeWords; i++) { 124 int word = vals[i]; 125 data[bitLength >>> 5] |= word >>> shift; 126 bitLength += 32; 127 data[bitLength >>> 5] = word << (32 - shift); 128 } 129 if (tailBits > 0) 130 appendBits(vals[wholeWords] >>> (32 - tailBits), tailBits); 131 } 132 } 133 134 } 135