/*
MIT License
Copyright (c) 2023 Affolter Matias
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
*/
function BitArray(s) {
s = (s | 0) >>> 0;
this.l_ = s|0;
this.a_ = new Uint32Array((this.l_ + 31 | 0) >>> 5);
this.M_OR_ = Uint32Array.of(
0b00000000000000000000000000000001,
0b00000000000000000000000000000010,
0b00000000000000000000000000000100,
0b00000000000000000000000000001000,
0b00000000000000000000000000010000,
0b00000000000000000000000000100000,
0b00000000000000000000000001000000,
0b00000000000000000000000010000000,
0b00000000000000000000000100000000,
0b00000000000000000000001000000000,
0b00000000000000000000010000000000,
0b00000000000000000000100000000000,
0b00000000000000000001000000000000,
0b00000000000000000010000000000000,
0b00000000000000000100000000000000,
0b00000000000000001000000000000000,
0b00000000000000010000000000000000,
0b00000000000000100000000000000000,
0b00000000000001000000000000000000,
0b00000000000010000000000000000000,
0b00000000000100000000000000000000,
0b00000000001000000000000000000000,
0b00000000010000000000000000000000,
0b00000000100000000000000000000000,
0b00000001000000000000000000000000,
0b00000010000000000000000000000000,
0b00000100000000000000000000000000,
0b00001000000000000000000000000000,
0b00010000000000000000000000000000,
0b00100000000000000000000000000000,
0b01000000000000000000000000000000,
0b10000000000000000000000000000000
);
this.M_AND_ = Uint32Array.of(
0b11111111111111111111111111111110,
0b11111111111111111111111111111101,
0b11111111111111111111111111111011,
0b11111111111111111111111111110111,
0b11111111111111111111111111101111,
0b11111111111111111111111111011111,
0b11111111111111111111111110111111,
0b11111111111111111111111101111111,
0b11111111111111111111111011111111,
0b11111111111111111111110111111111,
0b11111111111111111111101111111111,
0b11111111111111111111011111111111,
0b11111111111111111110111111111111,
0b11111111111111111101111111111111,
0b11111111111111111011111111111111,
0b11111111111111110111111111111111,
0b11111111111111101111111111111111,
0b11111111111111011111111111111111,
0b11111111111110111111111111111111,
0b11111111111101111111111111111111,
0b11111111111011111111111111111111,
0b11111111110111111111111111111111,
0b11111111101111111111111111111111,
0b11111111011111111111111111111111,
0b11111110111111111111111111111111,
0b11111101111111111111111111111111,
0b11111011111111111111111111111111,
0b11110111111111111111111111111111,
0b11101111111111111111111111111111,
0b11011111111111111111111111111111,
0b10111111111111111111111111111111,
0b01111111111111111111111111111111
);
}
Object.defineProperty(BitArray.prototype, 'readFourBytes', {
get: function() {
"use strict";
return function(i) {
"use strict";
i = (i | 0) >>> 0;
var a = [], b = this.a_[(i | 0) >>> 5];
if((b & this.M_OR_[0]|0) == (this.M_OR_[0]|0)){ a.push(i|0) }
if((b & this.M_OR_[1]|0) == (this.M_OR_[1]|0)){ a.push(i+1|0) }
if((b & this.M_OR_[2]|0) == (this.M_OR_[2]|0)){ a.push(i+2|0) }
if((b & this.M_OR_[3]|0) == (this.M_OR_[3]|0)){ a.push(i+3|0) }
if((b & this.M_OR_[4]|0) == (this.M_OR_[4]|0)){ a.push(i+4|0) }
if((b & this.M_OR_[5]|0) == (this.M_OR_[5]|0)){ a.push(i+5|0) }
if((b & this.M_OR_[6]|0) == (this.M_OR_[6]|0)){ a.push(i+6|0) }
if((b & this.M_OR_[7]|0) == (this.M_OR_[7]|0)){ a.push(i+7|0) }
if((b & this.M_OR_[8]|0) == (this.M_OR_[8]|0)){ a.push(i+8|0) }
if((b & this.M_OR_[9]|0) == (this.M_OR_[9]|0)){ a.push(i+9|0) }
if((b & this.M_OR_[10]|0) == (this.M_OR_[10]|0)){ a.push(i+10|0) }
if((b & this.M_OR_[11]|0) == (this.M_OR_[11]|0)){ a.push(i+11|0) }
if((b & this.M_OR_[12]|0) == (this.M_OR_[12]|0)){ a.push(i+12|0) }
if((b & this.M_OR_[13]|0) == (this.M_OR_[13]|0)){ a.push(i+13|0) }
if((b & this.M_OR_[14]|0) == (this.M_OR_[14]|0)){ a.push(i+14|0) }
if((b & this.M_OR_[15]|0) == (this.M_OR_[15]|0)){ a.push(i+15|0) }
if((b & this.M_OR_[16]|0) == (this.M_OR_[16]|0)){ a.push(i+16|0) }
if((b & this.M_OR_[17]|0) == (this.M_OR_[17]|0)){ a.push(i+17|0) }
if((b & this.M_OR_[18]|0) == (this.M_OR_[18]|0)){ a.push(i+18|0) }
if((b & this.M_OR_[19]|0) == (this.M_OR_[19]|0)){ a.push(i+19|0) }
if((b & this.M_OR_[20]|0) == (this.M_OR_[20]|0)){ a.push(i+20|0) }
if((b & this.M_OR_[21]|0) == (this.M_OR_[21]|0)){ a.push(i+21|0) }
if((b & this.M_OR_[22]|0) == (this.M_OR_[22]|0)){ a.push(i+22|0) }
if((b & this.M_OR_[23]|0) == (this.M_OR_[23]|0)){ a.push(i+23|0) }
if((b & this.M_OR_[24]|0) == (this.M_OR_[24]|0)){ a.push(i+24|0) }
if((b & this.M_OR_[25]|0) == (this.M_OR_[25]|0)){ a.push(i+25|0) }
if((b & this.M_OR_[26]|0) == (this.M_OR_[26]|0)){ a.push(i+26|0) }
if((b & this.M_OR_[27]|0) == (this.M_OR_[27]|0)){ a.push(i+27|0) }
if((b & this.M_OR_[28]|0) == (this.M_OR_[28]|0)){ a.push(i+28|0) }
if((b & this.M_OR_[29]|0) == (this.M_OR_[29]|0)){ a.push(i+29|0) }
if((b & this.M_OR_[30]|0) == (this.M_OR_[30]|0)){ a.push(i+30|0) }
if((b & this.M_OR_[31]|0) == (this.M_OR_[31]|0)){ a.push(i+31|0) }
return a;
}},
enumerable: false,
configurable: false
});
Object.defineProperty(BitArray.prototype, 'readBit', {
get: function() {
"use strict";
return function(i) {
"use strict";
i = (i | 0) >>> 0;
var m_or = this.M_OR_[i & 31];
i = (i | 0) >>> 5;
return (this.a_[i|0] & m_or | 0) == (m_or|0);
}},
enumerable: false,
configurable: false
});
Object.defineProperty(BitArray.prototype, 'writeBit1', {
get: function() {
"use strict";
return function(i) {
"use strict";
i = (i | 0) >>> 0;
var m_or = this.M_OR_[i & 31];
i = (i | 0) >>> 5;
this.a_[i|0] = this.a_[i|0] | m_or;
}},
enumerable: false,
configurable: false
});
Object.defineProperty(BitArray.prototype, 'writeBit0', {
get: function() {
"use strict";
return function(i) {
"use strict";
i = (i | 0) >>> 0;
var m_and = this.M_AND_[i & 31];
i = (i | 0) >>> 5;
this.a_[i|0] = this.a_[i|0] & m_and;
}},
enumerable: false,
configurable: false
});
Object.defineProperty(BitArray.prototype, 'clear', {
get: function() {
"use strict";
return function() {
"use strict";
this.a_.fill(0);
}},
enumerable: false,
configurable: false
});
Object.defineProperty(BitArray.prototype, 'length', {
get: function() {
"use strict";
return (this.l_ | 0) >>> 0;
},
enumerable: false,
configurable: false
});
Intro
The realm of pixel art is one of intricate detail, where each pixel serves a unique purpose to create a cohesive and expressive piece of art. In the world of digital art, this means managing the state of hundreds of thousands of pixels, each with a binary state: selected or not selected. To accomplish this efficiently, the digital art world needed a tool that could process these pixels quickly and effortlessly. Enter the BitArray.
The BitArray is a JavaScript class that we designed to serve as a fast and efficient way to keep track of the state of each pixel in a pixel art piece. Leveraging the power of bitwise operations and 32-bit integers, the BitArray is capable of processing rows of pixels at a time, resulting in a tremendous increase in speed.
Here's how it works.
In the given code, the >>> operator is used as a bitwise right shift with zero fill. This operator performs a logical shift to the right by the specified number of bits and fills the leftmost bits with zeros.
In the context of the code, the expression (s | 0) >>> 0 is used to convert the input s to an unsigned 32-bit integer. This ensures that the variable s is treated as an unsigned value, regardless of its original sign.
To understand how the bitshift 5 (>>> 5) is used to divide by 32, let's break down the process step by step:
The expression (i | 0) >>> 5 is used to calculate the index of the group or row of four bytes in the readFourBytes function. Here, i represents the input index.
(i | 0) is performed to ensure i is treated as a signed 32-bit integer.
>>> 5 is the bitwise right shift operation that shifts the binary representation of (i | 0) 5 positions to the right. This effectively divides (i | 0) by 2^5, which is 32.
The result of the bitwise right shift is used as the index to access the corresponding element in the this.a_ array.
Now, let's focus on the expression & 31 that appears alongside the bitshift 5 operation in the code. This expression is used to calculate the remainder of the division by 32 (which is equivalent to the value obtained from the last 5 bits of the binary representation of the number).
For example, if the result of the bitshift operation (i | 0) >>> 5 is 36, the binary representation of 36 is 0b100100. By applying the bitwise AND operation & 31, the result is obtained by taking the last 5 bits of the binary representation: 0b100100 & 0b011111, which equals 4 or (0b100).
In the code, the bitwise AND operation & 31 is used to determine the specific position within the group or row of four bytes. It helps identify which bit within the 32-bit value stored in this.a_ needs to be checked or modified.
In summary, the bitshift 5 (>>> 5) operation is used to divide a number by 32, and the expression & 31 is used to obtain the remainder of the division, which represents the index or position within a group of four bytes. These operations are utilized to access and manipulate specific bits in the this.a_ array within the given code.
Initialization
The BitArray takes a size parameter, s, which represents the total number of bits (or pixels) to be managed. This size is bitwise shifted to the right by zero, ensuring it is treated as a 32-bit integer. The function then initializes an array of 32-bit unsigned integers (Uint32Array), the length of which is the ceiling value of the size divided by 32. This is our bit array.
Bit Masking
The class holds two 32-length Uint32Arrays, M_OR_ and M_AND_, which serve as our bit masks. Each element in these arrays corresponds to a bit in a 32-bit integer. M_OR_ is used to set a bit to 1, and M_AND_ is used to set a bit to 0. These masks leverage the power of bitwise OR and AND operations, respectively.
Read/Write Operations
We've designed BitArray with several prototype functions to interact with the data. The 'readFourBytes' function retrieves a 32-bit chunk from the array and determines which bits are set. The 'readBit' function reads a single bit. The 'writeBit1' and 'writeBit0' functions are used to set a bit to 1 or 0, respectively.
Use Case: Pixel Art
In the context of pixel art, imagine each bit in the BitArray representing a pixel's state: selected (1) or not selected (0). This bit array allows us to quickly scan through each row of pixels (32 pixels at a time thanks to our choice of 32-bit integers) and check whether a pixel is selected or not.
This solution dramatically accelerates operations on pixel art up to 512x512 pixels in size, effectively handling a whopping 262,144 individual pixel states! Additionally, by using bit manipulation techniques, we're able to achieve this in a memory-efficient manner.
In conclusion, the BitArray class is a stellar example of how computer science concepts like bitwise operations can be leveraged in creative fields like digital art to improve performance, efficiency, and manageability. From managing pixel states in pixel art to potentially other applications in various fields, the BitArray stands as a testament to the harmony of art and science.
Harnessing BitArrays for Efficient Pixel Selection in Pixel Art: SetFixed
/*
MIT License
Copyright (c) 2023 Affolter Matias
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
*/
var SetFixed = function(size){
"use strict";
if (!(this instanceof SetFixed)) {
return new SetFixed(size);
}
if(typeof size == "object") {
this.set_ = new Set(Array.from(size));
this.s_ = this.set_.size;
this.indexes_ = Array.from(this.set_);
this.max_ = 0;
for(var i = 0, l = this.indexes_.length|0; (i|0) < (l|0); i = i + 1 | 0){if((this.max_|0) < (this.indexes_[i|0]|0)){ this.max_ = this.indexes_[i|0]|0; }}
this.a_ = new BitArray(this.max_);
for(var i = 0, l = this.indexes_.length|0; (i|0) < (l|0); i = i + 1 | 0){this.a_.writeBit1(this.indexes_[i|0]|0); }
delete this.set_;
delete this.indexes_;
delete this.max_;
}else {
this.a_ = new BitArray(size);
this.s_ = 0;
}
};
Object.defineProperty(SetFixed.prototype, 'size', {
get: function() {
"use strict";
return (this.s_ | 0) >>> 0;
},
enumerable: false,
configurable: false
});
Object.defineProperty(SetFixed.prototype, 'length', {
get: function() {
"use strict";
return (this.a_.length | 0) >>> 0;
},
enumerable: false,
configurable: false
});
Object.defineProperty(SetFixed.prototype, 'indexes', {
get: function() {
"use strict";
var a = [], l = this.length|0, i = 0;
for (; (i|0) < (l|0); i = (i + 32 | 0)>>>0) {
a.push.apply(a, this.a_.readFourBytes(i|0));
}
return a;
},
enumerable: false,
configurable: false
});
Object.defineProperty(SetFixed.prototype, 'has', {
get: function() { "use strict"; return function(i) {
"use strict";
i = (i|0) >>> 0;
return this.a_.readBit(i|0);
}},
enumerable: false,
configurable: false
});
Object.defineProperty(SetFixed.prototype, 'add', {
get: function() { "use strict"; return function(i) {
"use strict";
i = (i|0) >>> 0;
if((this.length|0) < (i|0)){
this.a_ = new BitArray(i+i|0);
var a = this.indexes, l = a.length|0, x = 0;
for(;(x|0)<(l|0); x = x + 1) {
this.a_.writeBit1(a[x|0]|0);
}
this.s_ = (a.length|0)>>>0;
}
if(!this.a_.readBit(i | 0)){
this.s_ = (this.s_ + 1 | 0) >>> 0;
}
this.a_.writeBit1(i | 0);
}},
enumerable: false,
configurable: false
});
Object.defineProperty(SetFixed.prototype, 'delete', {
get: function() { "use strict"; return function(i) {
"use strict";
i = (i|0) >>> 0;
if(this.a_.readBit(i | 0)){
this.a_.writeBit0(i | 0);
this.s_ = (this.s_ - 1 | 0) >>> 0;
}
}},
enumerable: false,
configurable: false
});
Object.defineProperty(SetFixed.prototype, 'clear', {
get: function() { "use strict"; return function() {
"use strict";
this.a_.clear();
this.s_ = 0;
}}
});
Object.defineProperty(SetFixed.prototype, 'forEach', {
get: function() {
"use strict"; return function(func) {
"use strict";
this.indexes.forEach(func);
}
},
enumerable: false,
configurable: false
});
Object.defineProperty(SetFixed.prototype, 'map', {
get: function() {
"use strict";
return function(func) {
"use strict";
return this.indexes.map(func);
}},
enumerable: false,
configurable: false
});
Object.defineProperty(SetFixed.prototype, 'filter', {
get: function() {
"use strict";
return function(func) {
"use strict";
return this.indexes.filter(func);
}},
enumerable: false,
configurable: false
});
Welcome, pixel art enthusiasts, software engineers, and all those fascinated by the artistry of bits and pixels! Today, we're delving into an innovative way of handling pixel selection in pixel art. We're exploring the powerful concept of the BitArray, as implemented in the JavaScript class SetFixed. This class is geared to offer a more efficient way to store and manipulate pixel selections in a pixel art canvas of up to 512x512 pixels. Are you ready to uncover the magic beneath the pixels? Let's get started!
The Purpose of BitArray in Pixel Art
In the world of pixel art, every pixel matters. Each tiny square plays its part in forming the bigger picture. So how can we track which pixels are selected in a canvas of up to 512x512 pixels in an efficient way? This is where the BitArray comes into play.
The BitArray serves as a compact, efficient way to store boolean values—true (selected) or false (not selected)—for each pixel in our canvas. Instead of a bulky data structure, the BitArray uses binary numbers, each bit representing the status of a pixel. The result? A compact, fast, and memory-efficient data structure that can quickly tell you the state of any pixel in the canvas.
SetFixed: A Masterclass in Efficiency
The SetFixed JavaScript class we're going to introduce is designed around this BitArray concept. When creating an instance of SetFixed, you can initialize it with a specific size or an existing Set object.
The size parameter is highly significant. In our pixel art context, it corresponds to the total number of pixels in the canvas (512x512 for a maxed-out canvas). When initialized, SetFixed creates a new BitArray of the specified size, each bit in the BitArray representing the selection status of a corresponding pixel.
If SetFixed is initialized with an existing Set object, it first converts the Set to an Array. Then, it identifies the maximum value in the Array, which will represent the size of the BitArray. Following this, SetFixed creates a new BitArray of this size, again mapping each bit in the BitArray to a pixel's selection status in the canvas.
The 32-bit Magic
The true genius of SetFixed lies in its handling of 32-bit numbers. Instead of writing or reading one bit at a time, SetFixed can process 32 bits simultaneously—equivalent to scanning an entire 'row' of 32 pixels in one operation! This massively speeds up operations, drastically reducing the time it takes to scan the whole canvas.
By using methods such as readFourBytes, writeBit1, and writeBit0, SetFixed is able to manipulate the BitArray and thus the canvas efficiently. Furthermore, through encapsulation and JavaScript's object properties, SetFixed offers various intuitive ways to interact with the BitArray, such as getting the size, length, indexes of the set, and checking if a certain pixel is selected (has).
In addition, SetFixed allows you to add (add) or delete (delete) elements, clear (clear) the whole set, and even apply high-level functions such as forEach, map, and filter on the selected pixels.
Conclusion
In summary, SetFixed offers an elegant, efficient solution for handling pixel selection in pixel art using a BitArray. Its use of 32-bit numbers accelerates operations, making it a highly performance-oriented solution. Whether you're a pixel artist looking to optimize your tools or a developer seeking to implement an efficient data structure
Top comments (1)
I hope Google once will tell us: