1 /*
2  * Copyright (C) 2015-2017, by Laszlo Szeremi under the Boost license.
3  *
4  * Pixel Perfect Engine, AdvancedBitArray module
5  */
6 
7 module PixelPerfectEngine.system.advBitArray;
8 import std.stdio;
9 /**
10 * Mainly intended for collision detection, can be used for other purposes too.
11 * DEPRECATED! Poorly designed, so better preexisting solutions will replace it.
12 */
13 public class AdvancedBitArray{
14 	private static const ubyte[8] maskData = [0b11111110,0b11111101,0b11111011,0b11110111,0b11101111,0b11011111,0b10111111,0b01111111];
15 	protected void[] rawData;
16 	protected size_t length;
17 
18 
19 	this(size_t length){
20 		setLength(length);
21 
22 	}
23 	this(void[] data, int l){
24 		rawData = data;
25 		rawData.length += 4;
26 		if(rawData.length % 4){
27 			rawData.length += 4 - (rawData.length % 4);
28 		}
29 		length = l;
30 	}
31 	//this(bool[] data){}
32 
33 	public size_t getLenght(){
34 		return length;
35 	}
36 
37 	public void setLength(size_t l){
38 		//test if resizing needed
39 		//if(length == l) return;
40 		/+else if(length < l){
41 			if((l + 32) / 8 > rawData.length){
42 				rawData.length = (l + 32 + (32 - l%32)) / 8;
43 			}
44 		}else{
45 			for(int i = l ; i < length ; i++){
46 				this[i] = false;
47 			}+/
48 		rawData.length = (l + 32 + (32 - l%32)) / 8;
49 		/+}+/
50 		this.length = l;
51 	}
52 	bool opEquals()(auto ref const AdvancedBitArray o) {
53 		for(int i ; i < rawData.length ; i += 4){
54 			if(cast(uint)rawData[i] != cast(uint)o.rawData[i]) return false;
55 		}
56 		return true;
57 	}
58 	AdvancedBitArray opBinary(string op)(int rhs){
59 		static if(op == ">>"){
60 			int byteShift = rhs / 8, bitShift = rhs % 8;
61 			AdvancedBitArray result = new AdvancedBitArray(this.length);
62 			//result.length = rawData.length;
63 			if(bitShift == 0){
64 				for(int i ; i < rawData.length - byteShift ; i+=4){
65 					*cast(uint*)(result.rawData.ptr + i + byteShift) = *cast(uint*)(rawData.ptr + i);
66 				}
67 			}else{
68 				for(int i ; i < rawData.length - byteShift ; i+=4){
69 					uint dA = *cast(uint*)(rawData.ptr + i), dB = i == 0 ? 0 : *cast(uint*)(rawData.ptr + i - 1);
70 					dA >>= bitShift;
71 					dB <<= (32-bitShift);
72 					*cast(uint*)(result.rawData.ptr + i + byteShift) = dA || dB;
73 				}
74 			}
75 			return result;
76 		}else static if(op == "<<"){
77 			int byteShift = rhs / 8, bitShift = rhs % 8;
78 			AdvancedBitArray result = new AdvancedBitArray(this.length);
79 			//result.length = rawData.length;
80 			if(bitShift == 0){
81 				for(int i ; i < rawData.length - byteShift ; i+=4){
82 					*cast(uint*)(result.rawData.ptr + i) = *cast(uint*)(rawData.ptr + i + byteShift);
83 				}
84 			}else{
85 				for(int i ; i < rawData.length - byteShift ; i+=4){
86 					uint dA = *cast(uint*)(rawData.ptr + i + byteShift), dB = *cast(uint*)(rawData.ptr + i + byteShift + 1);
87 					dA<<=bitShift;
88 					dB>>=(32-bitShift);
89 					*cast(uint*)(result.rawData.ptr + i + byteShift) = dA || dB;
90 				}
91 			}
92 			return result;
93 		}else static assert(0, "Operator "~op~" not implemented");
94 	}
95 	AdvancedBitArray opBinary(string op)(AdvancedBitArray rhs){
96 		static if(op == "&"){
97 			AdvancedBitArray result = new AdvancedBitArray(length);
98 			for(int i ; i < rawData.length ; i+=4){
99 				*cast(uint*)(result.rawData.ptr + i) = *cast(uint*)(rawData.ptr + i) & *cast(uint*)(rhs.rawData.ptr + i);
100 			}
101 			return result;
102 		}else static if(op == "|"){
103 			AdvancedBitArray result = new AdvancedBitArray(length);
104 			for(int i ; i < rawData.length ; i+=4){
105 				*cast(uint*)(result.rawData.ptr + i) = *cast(uint*)(rawData.ptr + i) | *cast(uint*)(rhs.rawData.ptr + i);
106 			}
107 			return result;
108 		}else static if(op == "^"){
109 			AdvancedBitArray result = new AdvancedBitArray(length);
110 			for(int i ; i < rawData.length ; i+=4){
111 				*cast(uint*)(result.rawData.ptr + i) = *cast(uint*)(rawData.ptr + i) ^ *cast(uint*)(rhs.rawData.ptr + i);
112 			}
113 			return result;
114 		}else static assert(0, "Operator "~op~" not implemented");
115 	}
116 
117 	public override string toString(){
118 		string result = "[";
119 		for(int i ; i < length ; i++){
120 			if(this[i]){
121 				result ~= "1";
122 			}else{
123 				result ~= "0";
124 			}
125 		}
126 		result ~= "]";
127 		return result;
128 	}
129 
130 	ref AdvancedBitArray opOPAssign(string op)(AdvancedBitArray rhs){
131 		static if(op == "&"){
132 			for(int i ; i < rawData.length ; i+=4){
133 				cast(uint)rawData[i] &= cast(uint)rhs.rawData[i];
134 			}
135 		}else static if(op == "|"){
136 			for(int i ; i < rawData.length ; i+=4){
137 				cast(uint)rawData[i] |= cast(uint)rhs.rawData[i];
138 			}
139 		}else static if(op == "^"){
140 			for(int i ; i < rawData.length ; i+=4){
141 				cast(uint)rawData[i] ^= cast(uint)rhs.rawData[i];
142 			}
143 		}else static if(op == "~"){
144 			/*int oldlength = length;
145 			this.setLength(length+rhs.length);*/
146 			if(length%8 == 0){
147 				rawData.length=length/8;
148 				rawData ~= rhs.rawData;
149 				this.setLength(length+rhs.length);
150 			}else{
151 
152 			}
153 		}else static assert(0, "Operator "~op~" not implemented");
154 	}
155 
156 	ref AdvancedBitArray opOPAssign(string op)(bool rhs){
157 		static if(op == "~"){
158 			this[length] = rhs;
159 			length++;
160 			if(length % 128 == 0){
161 				rawData.length += 16;
162 			}
163 		}else static assert(0, "Operator "~op~" not implemented");
164 	}
165 
166 	bool opIndexAssign(bool value, size_t i){
167 		size_t bytepos = i / 8, bitpos = i % 8;
168 		if(value){
169 			*cast(ubyte*)(rawData.ptr + bytepos) |= 0xFF - maskData[bitpos];
170 		}else{
171 			*cast(ubyte*)(rawData.ptr + bytepos) &= maskData[bitpos];
172 		}
173 		return value;
174 	}
175 
176 	bool opIndex(size_t i){
177 		size_t bytepos = i / 8, bitpos = i % 8;
178 		return (*cast(ubyte*)(rawData.ptr + bytepos) & (0xFF - maskData[bitpos])) != 0;
179 	}
180 	AdvancedBitArray opSlice(size_t i1, size_t i2){
181 		size_t bitShift = i1 % 8, bitShift2 = i2 % 8, byteShift = i1 / 8, byteShift2 = i2 / 8, l = i2 - i1, l2 = byteShift2 - byteShift;
182 		AdvancedBitArray result = new AdvancedBitArray(l);
183 		if(bitShift == 0){
184 			for(int i ; i < l2 ; i+=4){
185 				*cast(uint*)(result.rawData.ptr + i) = *cast(uint*)(rawData.ptr + i + byteShift);
186 			}
187 			if(l % 32 == 0){
188 				return result;
189 			}
190 		}else{
191 			for(int i ; i < l2 ; i+=4){
192 				*cast(uint*)(result.rawData.ptr + i) = *cast(uint*)(rawData.ptr + i + byteShift);
193 			}
194 		}
195 		return result;
196 	}
197 	/**
198 	* Tests multiple values at once. The intended algorithm didn't work as intended, replacement is coming in 0.9.2, in the meanwhile I'm using a slower but safer one.
199 	*/
200 	public bool test(int from, int length, AdvancedBitArray target, int tfrom){
201 		for(int i ; i < length ; i++){
202 			if(opIndex(from + i) && target[tfrom + i]){
203 				return true;
204 			}
205 		}
206 		/*int bitShiftA = from%8, bitShiftB = tfrom%8, bitlength = length%8, bitlength2 = length%32, byteShiftA = from/8, byteShiftB = tfrom/8, wordlength = length / 8;
207 		int i = -3;
208 		/*
209 		if(bitShiftA && bitShiftB){
210 			for(; i < wordlength; i++){
211 				int a = (*cast(ubyte*)(rawData.ptr + byteShiftA))<<bitShiftA | (*cast(ubyte*)(rawData.ptr + byteShiftA + 1))>>(8 - bitShiftA) & 0xff,
212 					b = (*cast(ubyte*)(target.rawData.ptr + byteShiftB))<<bitShiftB | (*cast(ubyte*)(target.rawData.ptr + byteShiftB + 1))>>(8 - bitShiftB) & 0xff;
213 				if(a & b){
214 					return true;
215 				}
216 			}
217 			if(bitlength){
218 				int a = (*cast(ubyte*)(rawData.ptr + byteShiftA))<<bitShiftA | (*cast(ubyte*)(rawData.ptr + byteShiftA + 1))>>(8 - bitShiftA) & 0xff,
219 					b = (*cast(ubyte*)(target.rawData.ptr + byteShiftB))<<bitShiftB | (*cast(ubyte*)(target.rawData.ptr + byteShiftB + 1))>>(8 - bitShiftB) & 0xff;
220 				a >>= bitlength;
221 				b >>= bitlength;
222 				if(a & b  & 0xff){
223 					return true;
224 				}
225 			}
226 		}else if(bitShiftB){
227 			for(; i < wordlength; i++){
228 				int a = (*cast(ubyte*)(rawData.ptr + byteShiftA)),
229 					b = (*cast(ubyte*)(target.rawData.ptr + byteShiftB))<<bitShiftB | (*cast(ubyte*)(target.rawData.ptr + byteShiftB + 1))>>(8 - bitShiftB) & 0xff;
230 				if(a & b){
231 					return true;
232 				}
233 			}
234 			if(bitlength){
235 				int a = (*cast(ubyte*)(rawData.ptr + byteShiftA)),
236 					b = (*cast(ubyte*)(target.rawData.ptr + byteShiftB))<<bitShiftB | (*cast(ubyte*)(target.rawData.ptr + byteShiftB + 1))>>(8 - bitShiftB) & 0xff;
237 				a >>= bitlength;
238 				b >>= bitlength;
239 				if(a & b  & 0xff){
240 					return true;
241 				}
242 			}
243 		}else if(bitShiftA){
244 			for(; i < wordlength; i++){
245 				int a = (*cast(ubyte*)(rawData.ptr + byteShiftA))<<bitShiftA | (*cast(ubyte*)(rawData.ptr + byteShiftA + 1))>>(8 - bitShiftA) & 0xff,
246 					b = (*cast(ubyte*)(target.rawData.ptr + byteShiftB));
247 				if(a & b){
248 					return true;
249 				}
250 			}
251 			if(bitlength){
252 				int a = (*cast(ubyte*)(rawData.ptr + byteShiftA))<<bitShiftA | (*cast(ubyte*)(rawData.ptr + byteShiftA + 1))>>(8 - bitShiftA) & 0xff,
253 					b = (*cast(ubyte*)(target.rawData.ptr + byteShiftB));
254 				a >>= bitlength;
255 				b >>= bitlength;
256 				if(a & b & 0xff){
257 					return true;
258 				}
259 			}
260 		}else{
261 			for(; i < wordlength; i++){
262 				int a = (*cast(ubyte*)(rawData.ptr + byteShiftA)),
263 					b = (*cast(ubyte*)(target.rawData.ptr + byteShiftB));
264 				if(a & b){
265 					return true;
266 				}
267 			}
268 			if(bitlength){
269 				int a = (*cast(ubyte*)(rawData.ptr + byteShiftA)),
270 					b = (*cast(ubyte*)(target.rawData.ptr + byteShiftB));
271 				a >>= bitlength;
272 				b >>= bitlength;
273 				if(a & b & 0xff){
274 					return true;
275 				}
276 			}
277 		}*/
278 
279 		/*if(bitShiftA && bitShiftB){
280 			for( ; i < wordlength - 7 ; i+=4){
281 				uint a = (*cast(uint*)(rawData.ptr + (byteShiftA)+i))<<bitShiftA | (*cast(uint*)(rawData.ptr + (byteShiftA)+1+i))>>(32-bitShiftA),
282 					b = (*cast(uint*)(target.rawData.ptr + (byteShiftB)+i))<<bitShiftB | (*cast(uint*)(target.rawData.ptr + (byteShiftB)+1+i))>>(32-bitShiftB);
283 				//writeln(a,',',b);
284 				if((a & b)){
285 					return true;
286 				}
287 			}
288 			if(i < wordlength - 3 || bitlength){
289 				uint a = (*cast(uint*)(rawData.ptr + (byteShiftA)+i))<<bitShiftA | (*cast(uint*)(rawData.ptr + (byteShiftA)+3+i))>>(32-bitShiftA),
290 					b = (*cast(uint*)(target.rawData.ptr + (byteShiftB)+i))<<bitShiftB | (*cast(uint*)(target.rawData.ptr + (byteShiftB)+1+i))>>(32-bitShiftB);
291 				a >>= 32 - bitlength2;
292 				b >>= 32 - bitlength2;
293 				//writeln(a,',',b);
294 			if((a & b)){
295 				return true;
296 			}
297 		}
298 		}else if(bitShiftB){
299 			for( ; i < wordlength - 7 ; i+=4){
300 				uint a = (*cast(uint*)(rawData.ptr + (byteShiftA)+i)<<bitShiftA) ,
301 					b = (*cast(uint*)(target.rawData.ptr + (byteShiftB)+i))<<bitShiftB | (*cast(uint*)(target.rawData.ptr + (byteShiftB)+3+i))>>(32-bitShiftB);
302 				//writeln(a,',',b);
303 				if(!(a & b)){
304 					return true;
305 				}
306 			}
307 			if(i < wordlength - 3 || bitlength){
308 				uint a = (*cast(uint*)(rawData.ptr + (byteShiftA)+i)<<bitShiftA) ,
309 					b = (*cast(uint*)(target.rawData.ptr + (byteShiftB)+i))<<bitShiftB | (*cast(uint*)(target.rawData.ptr + (byteShiftB)+3+i))>>(32-bitShiftB);
310 				a >>= 32 - bitlength2;
311 				b >>= 32 - bitlength2;
312 				//writeln(a,',',b);
313 				if((a & b)){
314 					return true;
315 				}
316 			}
317 		}else if(bitShiftA){
318 			for( ; i < wordlength - 7 ; i+=4){
319 				uint a = (*cast(uint*)(rawData.ptr + (byteShiftA)+i))<<bitShiftA | (*cast(uint*)(rawData.ptr + (byteShiftA)+4+i))>>(32-bitShiftA),
320 					b = (*cast(uint*)(target.rawData.ptr + (byteShiftB)+i)<<bitShiftB) ;
321 				//writeln(a,',',b);
322 				if((a & b)){
323 					return true;
324 				}
325 			}
326 			if(i < wordlength - 3 || bitlength){
327 				uint a = (*cast(uint*)(rawData.ptr + (byteShiftA)+i))<<bitShiftA | (*cast(uint*)(rawData.ptr + (byteShiftA)+4+i))>>(32-bitShiftA),
328 					b = (*cast(uint*)(target.rawData.ptr + (byteShiftB)+i)) ;
329 				a >>= 32 - bitlength2;
330 				b >>= 32 - bitlength2;
331 				//writeln(a,',',b);
332 				if((a & b)){
333 					return true;
334 				}
335 			}
336 		}else{
337 			for( ; i < wordlength - 7 ; i+=4){
338 				uint a = (*cast(uint*)(rawData.ptr + (byteShiftA)+i)) ,
339 					b = (*cast(uint*)(target.rawData.ptr + (byteShiftB)+i)) ;
340 				//writeln(a,',',b);
341 				if((a & b)){
342 					return true;
343 				}
344 			}
345 			if(i < wordlength - 3 || bitlength){
346 				uint a = (*cast(uint*)(rawData.ptr + (byteShiftA)+i)) ,
347 					b = (*cast(uint*)(target.rawData.ptr + (byteShiftB)+i)) ;
348 				//writeln(a,',',b);
349 				a >>= 32 - bitlength2;
350 				b >>= 32 - bitlength2;
351 				if((a & b)){
352 					return true;
353 				}
354 			}
355 		}/**/
356 		return false;
357 	}
358 	/*unittest{
359 		AdvancedBitArray a = new AdvancedBitArray([0b0,0b0,0b11111111,0b11111111,0b11111111,0b11111111,0b0,0b0],64);
360 		AdvancedBitArray b = new AdvancedBitArray([0b0,0b0,0b11111111,0b11111111,0b11111111,0b11111111,0b0,0b0],64);
361 
362 		assert(a.test(0,8,b,0) == false);
363 		assert(a.test(8,8,b,0) == false);
364 		assert(a.test(0,8,b,8) == false);
365 		assert(a.test(8,8,b,8) == false);
366 
367 		assert(a.test(0,16,b,0) == false);
368 
369 		assert(a.test(0,8,b,48) == false);
370 		assert(a.test(0,8,b,56) == false);
371 		assert(a.test(8,8,b,48) == false);
372 		assert(a.test(8,8,b,56) == false);
373 	}*/
374 }