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