omdl  v0.6.1
OpenSCAD Mechanical Design Library
math_bitwise.scad
Go to the documentation of this file.
1 //! Mathematical base-two bitwise binary functions.
2 /***************************************************************************//**
3  \file math_bitwise.scad
4  \author Roy Allen Sutton
5  \date 2017
6 
7  \copyright
8 
9  This file is part of [omdl] (https://github.com/royasutton/omdl),
10  an OpenSCAD mechanical design library.
11 
12  The \em omdl is free software; you can redistribute it and/or modify
13  it under the terms of the [GNU Lesser General Public License]
14  (http://www.gnu.org/licenses/lgpl.html) as published by the Free
15  Software Foundation; either version 2.1 of the License, or (at
16  your option) any later version.
17 
18  The \em omdl is distributed in the hope that it will be useful,
19  but WITHOUT ANY WARRANTY; without even the implied warranty of
20  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
21  Lesser General Public License for more details.
22 
23  You should have received a copy of the GNU Lesser General Public
24  License along with the \em omdl; if not, write to the Free Software
25  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
26  02110-1301, USA; or see <http://www.gnu.org/licenses/>.
27 
28  \details
29 
30  \ingroup math math_bitwise
31 *******************************************************************************/
32 
33 include <../datatypes/datatypes-base.scad>;
34 
35 //----------------------------------------------------------------------------//
36 /***************************************************************************//**
37  \page tv_math_bitwise Bitwise
38  \li \subpage tv_math_bitwise_s
39  \li \subpage tv_math_bitwise_r
40  \page tv_math_bitwise_s Script
41  \dontinclude math_bitwise_validate.scad
42  \skip include
43  \until end-of-tests
44  \page tv_math_bitwise_r Results
45  \include math_bitwise_validate.log
46 *******************************************************************************/
47 //----------------------------------------------------------------------------//
48 
49 //----------------------------------------------------------------------------//
50 /***************************************************************************//**
51  \addtogroup math
52  @{
53 
54  \defgroup math_bitwise Bitwise
55  \brief Base-two bitwise binary operations.
56 
57  \details
58 
59  See Wikipedia binary [numbers](https://en.wikipedia.org/wiki/Binary_number)
60  and [operations](https://en.wikipedia.org/wiki/Bitwise_operation)
61  for more information.
62 
63  See validation \ref tv_math_bitwise_r "results".
64  @{
65 *******************************************************************************/
66 //----------------------------------------------------------------------------//
67 
68 //! Test if a base-two bit position of an integer value equals a test bit.
69 /***************************************************************************//**
70  \param v <integer> An integer value.
71  \param b <integer> A base-two bit position.
72  \param t <bit> The bit test value [0|1].
73 
74  \returns <boolean> \b true when the base-two bit position of the integer
75  value equals \p t, otherwise returns \b false.
76 *******************************************************************************/
77 function bitwise_is_equal
78 (
79  v,
80  b,
81  t = 1
82 ) = ((floor(v / pow(2, b)) % 2) == t);
83 
84 //! Encode an integer value as a base-two list of bits.
85 /***************************************************************************//**
86  \param v <integer> An integer value.
87  \param w <integer> The minimum bit width.
88  \param bv (an internal recursion loop variable).
89 
90  \returns <bit-list> of bits base-two encoding of the integer value.
91  Returns \b undef when \p v or \p w is not an integer.
92 *******************************************************************************/
93 function bitwise_i2v
94 (
95  v,
96  w = 1,
97  bv = 1 // iteration bit value
98 ) = !is_integer(v) ? undef
99  : !is_integer(w) ? undef
100  : ((v == 0) && (bv >= pow(2, w))) ? empty_lst
101  : ((v % 2) > 0) ?
102  concat(bitwise_i2v(floor(v/2), w, bv*2), 1)
103  : concat(bitwise_i2v(floor(v/2), w, bv*2), 0);
104 
105 //! Decode a base-two list of bits to an integer value.
106 /***************************************************************************//**
107  \param v <bit-list> A value encoded as a base-two list of bits.
108 
109  \returns <integer> value encoding of the base-two list of bits.
110  Returns \b undef when \p v is not a list of bit values.
111 *******************************************************************************/
112 function bitwise_v2i
113 (
114  v
115 ) = is_empty(v) ? 0
116  : (first(v) == 1) ? bitwise_v2i(ntail(v)) + pow(2, len(v)-1)
117  : (first(v) == 0) ? bitwise_v2i(ntail(v))
118  : undef;
119 
120 //! Encode an integer value as a base-two string of bits.
121 /***************************************************************************//**
122  \param v <integer> An integer value.
123  \param w <integer> The minimum bit width.
124 
125  \returns <bit-string> of bits base-two encoding of the integer value.
126  Returns \b undef when \p v or \p w is not an integer.
127 *******************************************************************************/
128 function bitwise_i2s
129 (
130  v,
131  w = 1
132 ) = !is_integer(v) ? undef
133  : !is_integer(w) ? undef
134  : lstr(bitwise_i2v(v, w));
135 
136 //! Decode a base-two string of bits to an integer value.
137 /***************************************************************************//**
138  \param v <bit-string> A value encoded as a base-two string of bits.
139 
140  \returns <integer> value encoding of the base-two string of bits.
141  Returns \b undef when \p v is not a string of bit values.
142 *******************************************************************************/
143 function bitwise_s2i
144 (
145  v
146 ) = is_empty(v) ? 0
147  : (first(v) == "1") ? bitwise_s2i(ntail(v)) + pow(2, len(v)-1)
148  : (first(v) == "0") ? bitwise_s2i(ntail(v))
149  : undef;
150 
151 //! Decode the integer in a value at a shifted base-two bit mask of width-w.
152 /***************************************************************************//**
153  \param v <integer> An integer value.
154  \param w <integer> The bit mask width.
155  \param s <integer> The bit mask shift offset.
156 
157  \returns <integer> value of the \p w bits of \p v starting at bit
158  position \p s up to bit <tt>(w+s-1)</tt>.
159 *******************************************************************************/
160 function bitwise_imi
161 (
162  v,
163  w,
164  s
165 ) = bitwise_rsh(bitwise_and(v, bitwise_lsh(pow(2,w)-1, s)), s);
166 
167 //! Base-two bitwise AND operation for integers.
168 /***************************************************************************//**
169  \param v1 <integer> An integer value.
170  \param v2 <integer> An integer value.
171  \param bv (an internal recursion loop variable).
172 
173  \returns <integer> result of the base-two bitwise AND of \p v1 and \p v2.
174  Returns \b undef when \p v1 or \p v2 is not an integer.
175 *******************************************************************************/
176 function bitwise_and
177 (
178  v1,
179  v2,
180  bv = 1
181 ) = !is_integer(v1) ? undef
182  : !is_integer(v2) ? undef
183  : ((v1 + v2) == 0) ? 0
184  : (((v1 % 2) > 0) && ((v2 % 2) > 0)) ?
185  bitwise_and(floor(v1/2), floor(v2/2), bv*2) + bv
186  : bitwise_and(floor(v1/2), floor(v2/2), bv*2);
187 
188 //! Base-two bitwise OR operation for integers.
189 /***************************************************************************//**
190  \param v1 <integer> An integer value.
191  \param v2 <integer> An integer value.
192  \param bv (an internal recursion loop variable).
193 
194  \returns <integer> result of the base-two bitwise OR of \p v1 and \p v2.
195  Returns \b undef when \p v1 or \p v2 is not an integer.
196 *******************************************************************************/
197 function bitwise_or
198 (
199  v1,
200  v2,
201  bv = 1
202 ) = !is_integer(v1) ? undef
203  : !is_integer(v2) ? undef
204  : ((v1 + v2) == 0) ? 0
205  : (((v1 % 2) > 0) || ((v2 % 2) > 0)) ?
206  bitwise_or(floor(v1/2), floor(v2/2), bv*2) + bv
207  : bitwise_or(floor(v1/2), floor(v2/2), bv*2);
208 
209 //! Base-two bitwise XOR operation for integers.
210 /***************************************************************************//**
211  \param v1 <integer> An integer value.
212  \param v2 <integer> An integer value.
213  \param bv (an internal recursion loop variable).
214 
215  \returns <integer> result of the base-two bitwise XOR of \p v1 and \p v2.
216  Returns \b undef when \p v1 or \p v2 is not an integer.
217 *******************************************************************************/
218 function bitwise_xor
219 (
220  v1,
221  v2,
222  bv = 1
223 ) = !is_integer(v1) ? undef
224  : !is_integer(v2) ? undef
225  : ((v1 + v2) == 0) ? 0
226  : (((v1 % 2) > 0) != ((v2 % 2) > 0)) ?
227  bitwise_xor(floor(v1/2), floor(v2/2), bv*2) + bv
228  : bitwise_xor(floor(v1/2), floor(v2/2), bv*2);
229 
230 //! Base-two bitwise NOT operation for an integer.
231 /***************************************************************************//**
232  \param v <integer> An integer value.
233  \param w <integer> The minimum bit width.
234  \param bv (an internal recursion loop variable).
235 
236  \returns <integer> result of the base-two bitwise NOT of \p v.
237  Returns \b undef when \p v is not an integer.
238 *******************************************************************************/
239 function bitwise_not
240 (
241  v,
242  w = 1,
243  bv = 1
244 ) = !is_integer(v) ? undef
245  : ((v == 0) && (bv >= pow(2, w))) ? 0
246  : ((v % 2) > 0) ?
247  bitwise_not(floor(v/2), w, bv*2)
248  : bitwise_not(floor(v/2), w, bv*2) + bv;
249 
250 //! Base-two bitwise left-shift operation for an integer.
251 /***************************************************************************//**
252  \param v <integer> An integer value.
253  \param s <integer> The number of bits to shift.
254  \param bm (an internal recursion loop variable).
255  \param bv (an internal recursion loop variable).
256 
257  \returns <integer> result of the base-two bitwise left-shift of \p v
258  by \p s bits.
259  Returns \b undef when \p v or \p s is not an integer.
260 *******************************************************************************/
261 function bitwise_lsh
262 (
263  v,
264  s = 1,
265  bm = 1,
266  bv = 1
267 ) = !is_integer(v) ? undef
268  : !is_integer(s) ? undef
269  : (bm < v) ? bitwise_lsh(v, s, bm*2, bv) // max bit position
270  : (s > 0) ? bitwise_lsh(v*2, s-1, bm, bv) // shift value
271  : (bv > bm) ? 0
272  : ((v % 2) > 0) ? // encoded result
273  bitwise_lsh(floor(v/2), s, bm, bv*2) + bv
274  : bitwise_lsh(floor(v/2), s, bm, bv*2);
275 
276 //! Base-two bitwise right-shift operation for an integer.
277 /***************************************************************************//**
278  \param v <integer> An integer value.
279  \param s <integer> The number of bits to shift.
280 
281  \returns <integer> result of the base-two bitwise right-shift of \p v
282  by \p s bits.
283  Returns \b undef when \p v or \p s is not an integer.
284 *******************************************************************************/
285 function bitwise_rsh
286 (
287  v,
288  s = 1
289 ) = !is_integer(v) ? undef
290  : !is_integer(s) ? undef
291  : (s <= 0) ? v
292  : bitwise_rsh(floor(v/2), s-1);
293 
294 //! @}
295 //! @}
296 
297 //----------------------------------------------------------------------------//
298 // openscad-amu auxiliary scripts
299 //----------------------------------------------------------------------------//
300 
301 /*
302 BEGIN_SCOPE validate;
303  BEGIN_OPENSCAD;
304  include <console.scad>;
305  include <datatypes/datatypes_table.scad>;
306  include <math/math_bitwise.scad>;
307  include <validation.scad>;
308 
309  show_passing = true; // show passing tests
310  show_skipped = true; // show skipped tests
311 
312  echo( str("OpenSCAD Version ", version()) );
313 
314  // test-values columns
315  test_c =
316  [
317  ["id", "identifier"],
318  ["td", "description"],
319  ["tv", "test value"]
320  ];
321 
322  // test-values rows
323  test_r =
324  [
325  ["fac", "Function argument count", undef],
326  ["t01", "All undefined", [undef,undef]],
327  ["t02", "All empty lists", [empty_lst,empty_lst]],
328  ["t03", "test value 1", [254, 0]],
329  ["t04", "test value 2", [254, 1]],
330  ["t05", "test value 3", [255, 0]],
331  ["t06", "test value 4", [0, 255]],
332  ["t07", "test value 5", [126, 63]],
333  ["t08", "test value 6", [25, 10]],
334  ["t09", "test value 7", [1024, 512]],
335  ["t10", "test value 8", [4253, 315]],
336  ["t11", "test value 9", [835, 769]],
337  ["t12", "test value 10", [856, 625]]
338  ];
339 
340  test_ids = get_table_ridl( test_r );
341 
342  // expected columns: ("id" + one column for each test)
343  good_c = pmerge([concat("id", test_ids), concat("identifier", test_ids)]);
344 
345  // expected rows: ("golden" test results), use 'skip' to skip test
346  skip = -1; // skip test
347 
348  good_r =
349  [ // function
350  ["bitwise_is_equal_0", 2,
351  false, // t01
352  false, // t02
353  true, // t03
354  false, // t04
355  false, // t05
356  true, // t06
357  true, // t07
358  true, // t08
359  true, // t09
360  true, // t10
361  true, // t11
362  true // t12
363  ],
364  ["bitwise_is_equal_1", 2,
365  false, // t01
366  false, // t02
367  false, // t03
368  true, // t04
369  true, // t05
370  false, // t06
371  false, // t07
372  false, // t08
373  false, // t09
374  false, // t10
375  false, // t11
376  false // t12
377  ],
378  ["bitwise_i2v", 1,
379  undef, // t01
380  undef, // t02
381  [1,1,1,1,1,1,1,0], // t03
382  [1,1,1,1,1,1,1,0], // t04
383  [1,1,1,1,1,1,1,1], // t05
384  [0], // t06
385  [1,1,1,1,1,1,0], // t07
386  [1,1,0,0,1], // t08
387  [1,0,0,0,0,0,0,0,0,0,0], // t09
388  [1,0,0,0,0,1,0,0,1,1,1,0,1], // t10
389  [1,1,0,1,0,0,0,0,1,1], // t11
390  [1,1,0,1,0,1,1,0,0,0] // t12
391  ],
392  ["bitwise_i2v_v2i", 1,
393  undef, // t01
394  undef, // t02
395  254, // t03
396  254, // t04
397  255, // t05
398  0, // t06
399  126, // t07
400  25, // t08
401  1024, // t09
402  4253, // t10
403  835, // t11
404  856 // t12
405  ],
406  ["bitwise_i2s", 1,
407  undef, // t01
408  undef, // t02
409  "11111110", // t03
410  "11111110", // t04
411  "11111111", // t05
412  "0", // t06
413  "1111110", // t07
414  "11001", // t08
415  "10000000000", // t09
416  "1000010011101", // t10
417  "1101000011", // t11
418  "1101011000" // t12
419  ],
420  ["bitwise_i2s_s2i", 1,
421  undef, // t01
422  undef, // t02
423  254, // t03
424  254, // t04
425  255, // t05
426  0, // t06
427  126, // t07
428  25, // t08
429  1024, // t09
430  4253, // t10
431  835, // t11
432  856 // t12
433  ],
434  ["bitwise_imi_32", 1,
435  undef, // t01
436  undef, // t02
437  7, // t03
438  7, // t04
439  7, // t05
440  0, // t06
441  7, // t07
442  6, // t08
443  0, // t09
444  7, // t10
445  0, // t11
446  6 // t12
447  ],
448  ["bitwise_and", 2,
449  undef, // t01
450  undef, // t02
451  0, // t03
452  0, // t04
453  0, // t05
454  0, // t06
455  62, // t07
456  8, // t08
457  0, // t09
458  25, // t10
459  769, // t11
460  592 // t12
461  ],
462  ["bitwise_or", 2,
463  undef, // t01
464  undef, // t02
465  254, // t03
466  255, // t04
467  255, // t05
468  255, // t06
469  127, // t07
470  27, // t08
471  1536, // t09
472  4543, // t10
473  835, // t11
474  889 // t12
475  ],
476  ["bitwise_xor", 2,
477  undef, // t01
478  undef, // t02
479  254, // t03
480  255, // t04
481  255, // t05
482  255, // t06
483  65, // t07
484  19, // t08
485  1536, // t09
486  4518, // t10
487  66, // t11
488  297 // t12
489  ],
490  ["bitwise_not", 1,
491  undef, // t01
492  undef, // t02
493  1, // t03
494  1, // t04
495  0, // t05
496  1, // t06
497  1, // t07
498  6, // t08
499  1023, // t09
500  3938, // t10
501  188, // t11
502  167 // t12
503  ],
504  ["bitwise_lsh", 1,
505  undef, // t01
506  undef, // t02
507  508, // t03
508  508, // t04
509  510, // t05
510  0, // t06
511  252, // t07
512  50, // t08
513  2048, // t09
514  8506, // t10
515  1670, // t11
516  1712 // t12
517  ],
518  ["bitwise_rsh", 1,
519  undef, // t01
520  undef, // t02
521  127, // t03
522  127, // t04
523  127, // t05
524  0, // t06
525  63, // t07
526  12, // t08
527  512, // t09
528  2126, // t10
529  417, // t11
530  428 // t12
531  ]
532  ];
533 
534  // sanity-test tables
535  table_check( test_r, test_c, false );
536  table_check( good_r, good_c, false );
537 
538  // validate helper function and module
539  function get_value( vid ) = get_table_v(test_r, test_c, vid, "tv");
540  function gv( vid, e ) = get_value( vid )[e];
541  module run( fname, vid )
542  {
543  value_text = get_table_v(test_r, test_c, vid, "td");
544 
545  if ( get_table_v(good_r, good_c, fname, vid) != skip )
546  children();
547  else if ( show_skipped )
548  log_info( str("*skip*: ", vid, " '", fname, "(", value_text, ")'") );
549  }
550  module test( fname, fresult, vid )
551  {
552  value_text = get_table_v(test_r, test_c, vid, "td");
553  fname_argc = get_table_v(good_r, good_c, fname, "fac");
554  pass_value = get_table_v(good_r, good_c, fname, vid);
555 
556  test_pass = validate(cv=fresult, t="equals", ev=pass_value, pf=true);
557  farg_text = lstr(eappend(", ", rselect(get_value(vid), [0:fname_argc-1]), r=false, j=false, l=false));
558  test_text = validate(str(fname, "(", farg_text, ")=", pass_value), fresult, "equals", pass_value);
559 
560  if ( pass_value != skip )
561  {
562  if ( !test_pass )
563  log_warn( str(vid, "(", value_text, ") ", test_text) );
564  else if ( show_passing )
565  log_info( str(vid, " ", test_text) );
566  }
567  else if ( show_skipped )
568  log_info( str(vid, " *skip*: '", fname, "(", value_text, ")'") );
569  }
570 
571  // Indirect function calls would be very useful here!!!
572  run_ids = delete( test_ids, mv=["fac", "crp"] );
573  for (vid=run_ids) run("bitwise_is_equal_0",vid) test( "bitwise_is_equal_0", bitwise_is_equal(gv(vid,0),gv(vid,1),0), vid );
574  for (vid=run_ids) run("bitwise_is_equal_1",vid) test( "bitwise_is_equal_1", bitwise_is_equal(gv(vid,0),gv(vid,1),1), vid );
575  for (vid=run_ids) run("bitwise_i2v",vid) test( "bitwise_i2v", bitwise_i2v(gv(vid,0)), vid );
576  for (vid=run_ids) run("bitwise_i2v_v2i",vid) test( "bitwise_i2v_v2i", bitwise_v2i(bitwise_i2v(gv(vid,0))), vid );
577  for (vid=run_ids) run("bitwise_i2s",vid) test( "bitwise_i2s", bitwise_i2s(gv(vid,0)), vid );
578  for (vid=run_ids) run("bitwise_i2s_s2i",vid) test( "bitwise_i2s_s2i", bitwise_s2i(bitwise_i2s(gv(vid,0))), vid );
579  for (vid=run_ids) run("bitwise_imi_32",vid) test( "bitwise_imi_32", bitwise_imi(gv(vid,0),3,2), vid );
580  for (vid=run_ids) run("bitwise_and",vid) test( "bitwise_and", bitwise_and(gv(vid,0),gv(vid,1)), vid );
581  for (vid=run_ids) run("bitwise_or",vid) test( "bitwise_or", bitwise_or(gv(vid,0),gv(vid,1)), vid );
582  for (vid=run_ids) run("bitwise_xor",vid) test( "bitwise_xor", bitwise_xor(gv(vid,0),gv(vid,1)), vid );
583  for (vid=run_ids) run("bitwise_not",vid) test( "bitwise_not", bitwise_not(gv(vid,0)), vid );
584  for (vid=run_ids) run("bitwise_lsh",vid) test( "bitwise_lsh", bitwise_lsh(gv(vid,0)), vid );
585  for (vid=run_ids) run("bitwise_rsh",vid) test( "bitwise_rsh", bitwise_rsh(gv(vid,0)), vid );
586 
587  // end-of-tests
588  END_OPENSCAD;
589 
590  BEGIN_MFSCRIPT;
591  include --path "${INCLUDE_PATH}" {config_base,config_csg}.mfs;
592  include --path "${INCLUDE_PATH}" script_std.mfs;
593  END_MFSCRIPT;
594 END_SCOPE;
595 */
596 
597 //----------------------------------------------------------------------------//
598 // end of file
599 //----------------------------------------------------------------------------//
bitwise_and
function bitwise_and(v1, v2, bv=1)
Base-two bitwise AND operation for integers.
bitwise_s2i
function bitwise_s2i(v)
Decode a base-two string of bits to an integer value.
is_empty
function is_empty(v)
Test if an iterable value is empty.
is_integer
function is_integer(v)
Test if a value is an integer.
bitwise_not
function bitwise_not(v, w=1, bv=1)
Base-two bitwise NOT operation for an integer.
bitwise_i2v
function bitwise_i2v(v, w=1, bv=1)
Encode an integer value as a base-two list of bits.
empty_lst
empty_lst
A list with no values (the empty list).
Definition: constants.scad:80
bitwise_v2i
function bitwise_v2i(v)
Decode a base-two list of bits to an integer value.
lstr
function lstr(v)
Convert a list of values to a concatenated string.
first
function first(v)
Return the first element of an iterable value.
bitwise_is_equal
function bitwise_is_equal(v, b, t=1)
Test if a base-two bit position of an integer value equals a test bit.
bitwise_xor
function bitwise_xor(v1, v2, bv=1)
Base-two bitwise XOR operation for integers.
bitwise_imi
function bitwise_imi(v, w, s)
Decode the integer in a value at a shifted base-two bit mask of width-w.
bitwise_rsh
function bitwise_rsh(v, s=1)
Base-two bitwise right-shift operation for an integer.
bitwise_or
function bitwise_or(v1, v2, bv=1)
Base-two bitwise OR operation for integers.
bitwise_i2s
function bitwise_i2s(v, w=1)
Encode an integer value as a base-two string of bits.
ntail
function ntail(v, n=1)
Return a list containing all but the first n elements of an iterable value.
bitwise_lsh
function bitwise_lsh(v, s=1, bm=1, bv=1)
Base-two bitwise left-shift operation for an integer.