omdl  v1.0
OpenSCAD Mechanical Design Library
binary.scad
Go to the documentation of this file.
1 //! Base-2 binary numbers tests and operations.
2 /***************************************************************************//**
3  \file
4  \author Roy Allen Sutton
5  \date 2017-2023
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  \amu_define group_name (Binary Numbers)
31  \amu_define group_brief (Base-2 binary numbers tests and operations.)
32 
33  \amu_include (include/amu/doxyg_init_pd_gds_ipg.amu)
34 *******************************************************************************/
35 
36 // auto-tests (add to test results page)
37 /***************************************************************************//**
38  \amu_include (include/amu/validate_log.amu)
39  \amu_include (include/amu/validate_results.amu)
40 *******************************************************************************/
41 
42 // group(s) begin (test summary and includes-required)
43 /***************************************************************************//**
44  \amu_include (include/amu/doxyg_define_in_parent_open.amu)
45  \amu_include (include/amu/validate_summary.amu)
46  \amu_include (include/amu/includes_required.amu)
47 *******************************************************************************/
48 
49 // member-wide reference definitions
50 /***************************************************************************//**
51  \amu_define group_references
52  (
53  )
54 *******************************************************************************/
55 
56 // member-wide documentation and conventions
57 /***************************************************************************//**
58  \addtogroup \amu_eval(${group})
59  \details
60  \anchor \amu_eval(${group})_conventions
61  \par Conventions
62 
63  - All functions operate only on \b non-negative integers. Passing a
64  negative integer produces \b undef (after the recommended fix; before
65  the fix, it causes infinite recursion — see Correctness §2.1).
66  - Bit lists (\c <bit-list>) are stored \b LSB-first: the least-significant
67  bit occupies index 0 and the most-significant bit occupies the last index.
68  - The parameter \p _bv in binary_and(), binary_or(), binary_xor(),
69  binary_not(), and binary_i2v() is an \em internal recursion accumulator.
70  It must not be initialised by callers.
71  - The parameter \p bm in binary_ishl() is an \em internal bit-mask
72  accumulator. It must not be initialised by callers.
73  - binary_ishl() clips the result to the bit-width of the input \p v.
74  Use binary_iw2i() to extract a fixed-width window from a wider value.
75  - Empty \c <bit-list> or \c <bit-string> inputs return \b undef
76  (after the recommended fix) to distinguish the empty case from zero.
77 
78  See Wikipedia binary [numbers] and [operations] for more information.
79 
80  [numbers]: https://en.wikipedia.org/wiki/Binary_number
81  [operations]: https://en.wikipedia.org/wiki/Bitwise_operation
82 *******************************************************************************/
83 
84 //----------------------------------------------------------------------------//
85 // members
86 //----------------------------------------------------------------------------//
87 
88 //! Test if a binary bit position of an integer value equals a test bit.
89 /***************************************************************************//**
90  \param v <integer> An integer value.
91  \param b <integer> A binary bit position.
92  \param t <bit> The bit test value [0|1].
93 
94  \returns (1) <boolean> \b true when the binary bit position in \p v
95  specified by \p b equals \p t, otherwise returns
96  \b false.
97  (2) Returns \b undef if \p v or \p b is not an integer.
98 *******************************************************************************/
99 function binary_bit_is
100 (
101  v,
102  b,
103  t = 1
104 ) = !is_integer(v) ? undef
105  : !is_integer(b) ? undef
106  : ((floor(v / pow(2, b)) % 2) == t);
107 
108 //! Encode an integer value as a binary list of bits.
109 /***************************************************************************//**
110  \param v <integer> An integer value.
111  \param w <integer> The minimum bit width.
112  \param _bv (an internal recursion loop variable).
113 
114  \returns (1) <bit-list> of bits binary encoding of the integer value.
115  (2) Returns \b undef when \p v or \p w is not an integer.
116 
117  \details
118 
119  The bit-list will be the minimum required to represent the value. If
120  \p w is greater than the minimum required bits, then the value will
121  be padded with '0'.
122 
123  Bits are ordered \em most-significant-bit first: index \c 0 holds
124  the most significant bit and the last index holds the least
125  significant bit. For example, <tt>binary_i2v(6)</tt> returns
126  <tt>[1,1,0]</tt>, where <tt>[0]</tt>=MSB and <tt>[2]</tt>=LSB.
127 *******************************************************************************/
128 function binary_i2v
129 (
130  v,
131  w = 1,
132  // iteration bit value
133  _bv = 1
134 ) = !is_integer(v) ? undef
135  : !is_integer(w) ? undef
136  : ((v == 0) && (_bv >= pow(2, w))) ? empty_lst
137  : ((v % 2) > 0) ? concat(binary_i2v(floor(v/2), w, _bv*2), 1)
138  : concat(binary_i2v(floor(v/2), w, _bv*2), 0);
139 
140 //! Decode a binary list of bits to an integer value.
141 /***************************************************************************//**
142  \param v <bit-list> A value encoded as a binary list of bits.
143 
144  \returns (1) <integer> value encoding of the binary list of bits.
145  (2) Returns \b undef when \p v is not a list of bit values.
146 *******************************************************************************/
147 function binary_v2i
148 (
149  v
150 ) = is_empty(v) ? 0
151  // all must be '0' or '1'
152  : !all_oneof(v, [0, 1]) ? undef
153  : (first(v) == 1) ? binary_v2i(tailn(v)) + pow(2, len(v)-1)
154  : (first(v) == 0) ? binary_v2i(tailn(v))
155  : undef;
156 
157 //! Encode an integer value as a binary string of bits.
158 /***************************************************************************//**
159  \param v <integer> An integer value.
160  \param w <integer> The minimum bit width.
161 
162  \returns (1) <bit-string> of bits binary encoding of the integer value.
163  (2) Returns \b undef when \p v or \p w is not an integer.
164 *******************************************************************************/
165 function binary_i2s
166 (
167  v,
168  w = 1
169 ) = !is_integer(v) ? undef
170  : !is_integer(w) ? undef
171  : strl(binary_i2v(v, w));
172 
173 //! Decode a binary string of bits to an integer value.
174 /***************************************************************************//**
175  \param v <bit-string> A value encoded as a binary string of bits.
176 
177  \returns (1) <integer> value encoding of the binary string of bits.
178  (2) Returns \b undef when \p v is not a string of bit values.
179 *******************************************************************************/
180 function binary_s2i
181 (
182  v
183 ) = is_empty(v) ? 0
184  // all must be '0' or '1'
185  : !all_oneof(v, "01") ? undef
186  : (first(v) == "1") ? binary_s2i(strl(tailn(v))) + pow(2, len(v)-1)
187  : (first(v) == "0") ? binary_s2i(strl(tailn(v)))
188  : undef;
189 
190 //! Decode the binary bits of a bit window to an integer value.
191 /***************************************************************************//**
192  \param v <integer> An integer value.
193  \param s <integer> The bit window start offset.
194  \param w <integer> The bit window width.
195 
196  \returns (1) <integer> value of the \p w bits of \p v starting at bit
197  position \p s up to bit <tt>(w+s-1)</tt>.
198  (2) Returns \b undef when \p v, \p w, or \p s is not an
199  integer.
200 *******************************************************************************/
201 function binary_iw2i
202 (
203  v,
204  s,
205  w
206 ) = !is_integer(v) ? undef
207  : !is_integer(w) ? undef
208  : !is_integer(s) ? undef
209  : binary_ishr(binary_and(v, binary_ishl(pow(2,w)-1, s)), s);
210 
211 //! Base-2 binary AND operation for integers.
212 /***************************************************************************//**
213  \param v1 <integer> An integer value.
214  \param v2 <integer> An integer value.
215  \param _bv (an internal recursion loop variable).
216 
217  \returns (1) <integer> the binary AND of \p v1 and \p v2.
218  (2) Returns \b undef when \p v1 or \p v2 is not an integer.
219 *******************************************************************************/
220 function binary_and
221 (
222  v1,
223  v2,
224  _bv = 1
225 ) = !is_integer(v1) ? undef
226  : !is_integer(v2) ? undef
227  : ((v1 + v2) == 0) ? 0
228  : (((v1 % 2) > 0) && ((v2 % 2) > 0)) ?
229  binary_and(floor(v1/2), floor(v2/2), _bv*2) + _bv
230  : binary_and(floor(v1/2), floor(v2/2), _bv*2);
231 
232 //! Base-2 binary OR operation for integers.
233 /***************************************************************************//**
234  \param v1 <integer> An integer value.
235  \param v2 <integer> An integer value.
236  \param _bv (an internal recursion loop variable).
237 
238  \returns (1) <integer> the binary OR of \p v1 and \p v2.
239  (2) Returns \b undef when \p v1 or \p v2 is not an integer.
240 *******************************************************************************/
241 function binary_or
242 (
243  v1,
244  v2,
245  _bv = 1
246 ) = !is_integer(v1) ? undef
247  : !is_integer(v2) ? undef
248  : ((v1 + v2) == 0) ? 0
249  : (((v1 % 2) > 0) || ((v2 % 2) > 0)) ?
250  binary_or(floor(v1/2), floor(v2/2), _bv*2) + _bv
251  : binary_or(floor(v1/2), floor(v2/2), _bv*2);
252 
253 //! Base-2 binary XOR operation for integers.
254 /***************************************************************************//**
255  \param v1 <integer> An integer value.
256  \param v2 <integer> An integer value.
257  \param _bv (an internal recursion loop variable).
258 
259  \returns (1) <integer> the binary XOR of \p v1 and \p v2.
260  (2) Returns \b undef when \p v1 or \p v2 is not an integer.
261 *******************************************************************************/
262 function binary_xor
263 (
264  v1,
265  v2,
266  _bv = 1
267 ) = !is_integer(v1) ? undef
268  : !is_integer(v2) ? undef
269  : ((v1 + v2) == 0) ? 0
270  : (((v1 % 2) > 0) != ((v2 % 2) > 0)) ?
271  binary_xor(floor(v1/2), floor(v2/2), _bv*2) + _bv
272  : binary_xor(floor(v1/2), floor(v2/2), _bv*2);
273 
274 //! Base-2 binary NOT operation for an integer.
275 /***************************************************************************//**
276  \param v <integer> An integer value.
277  \param w <integer> The minimum bit width.
278  \param _bv (an internal recursion loop variable).
279 
280  \returns (1) <integer> the binary NOT of \p v.
281  (2) Returns \b undef when \p v or \p w is not an integer.
282 *******************************************************************************/
283 function binary_not
284 (
285  v,
286  w = 1,
287  _bv = 1
288 ) = !is_integer(v) ? undef
289  : !is_integer(w) ? undef
290  : ((v == 0) && (_bv >= pow(2, w))) ? 0
291  : ((v % 2) > 0) ?
292  binary_not(floor(v/2), w, _bv*2)
293  : binary_not(floor(v/2), w, _bv*2) + _bv;
294 
295 //! Base-2 binary left-shift operation for an integer.
296 /***************************************************************************//**
297  \param v <integer> A non-negative integer value.
298  \param s <integer> A non-negative number of bits to shift.
299 
300  \returns (1) <integer> the binary left-shift of \p v by \p s bits.
301  (2) Returns \b undef when \p v or \p s is not an integer
302  or when either is negative.
303 *******************************************************************************/
304 function binary_ishl
305 (
306  v,
307  s = 1
308 ) = !is_integer(v) ? undef
309  : !is_integer(s) ? undef
310  : (v < 0 || s < 0) ? undef
311  : floor(v * pow(2, s));
312 
313 //! Base-2 binary right-shift operation for an integer.
314 /***************************************************************************//**
315  \param v <integer> A non-negative integer value.
316  \param s <integer> The number of bits to shift.
317 
318  \returns (1) <integer> the binary right-shift of \p v by \p s bits.
319  (2) Returns \b undef when \p v or \p s is not an integer
320  or when either is negative.
321 *******************************************************************************/
322 function binary_ishr
323 (
324  v,
325  s = 1
326 ) = !is_integer(v) ? undef
327  : !is_integer(s) ? undef
328  : (v < 0 || s < 0) ? undef
329  : floor(v / pow(2, s));
330 
331 //! @}
332 //! @}
333 
334 //----------------------------------------------------------------------------//
335 // openscad-amu auxiliary scripts
336 //----------------------------------------------------------------------------//
337 
338 /*
339 BEGIN_SCOPE validate;
340  BEGIN_OPENSCAD;
341  include <omdl-base.scad>;
342  include <common/validation.scad>;
343 
344  echo( str("openscad version ", version()) );
345 
346  // test-values columns
347  test_c =
348  [
349  ["id", "identifier"],
350  ["td", "description"],
351  ["tv", "test value"]
352  ];
353 
354  // test-values rows
355  test_r =
356  [
357  ["fac", "Function argument count", undef],
358  ["t01", "All undefined", [undef,undef]],
359  ["t02", "All empty lists", [empty_lst,empty_lst]],
360  ["t03", "test value 1", [254, 0]],
361  ["t04", "test value 2", [254, 1]],
362  ["t05", "test value 3", [255, 0]],
363  ["t06", "test value 4", [0, 255]],
364  ["t07", "test value 5", [126, 63]],
365  ["t08", "test value 6", [25, 10]],
366  ["t09", "test value 7", [1024, 512]],
367  ["t10", "test value 8", [4253, 315]],
368  ["t11", "test value 9", [835, 769]],
369  ["t12", "test value 10", [856, 625]]
370  ];
371 
372  test_ids = table_get_row_ids( test_r );
373 
374  // expected columns: ("id" + one column for each test)
375  good_c = merge_p([concat("id", test_ids), concat("identifier", test_ids)]);
376 
377  // expected rows: ("golden" test results), use 'skip' to skip test
378  skip = -1; // skip test
379 
380  good_r =
381  [ // function
382  ["binary_bit_is_0", 2,
383  undef, // t01
384  undef, // t02
385  true, // t03
386  false, // t04
387  false, // t05
388  true, // t06
389  true, // t07
390  true, // t08
391  true, // t09
392  true, // t10
393  true, // t11
394  true // t12
395  ],
396  ["binary_bit_is_1", 2,
397  undef, // t01
398  undef, // t02
399  false, // t03
400  true, // t04
401  true, // t05
402  false, // t06
403  false, // t07
404  false, // t08
405  false, // t09
406  false, // t10
407  false, // t11
408  false // t12
409  ],
410  ["binary_i2v", 1,
411  undef, // t01
412  undef, // t02
413  [1,1,1,1,1,1,1,0], // t03
414  [1,1,1,1,1,1,1,0], // t04
415  [1,1,1,1,1,1,1,1], // t05
416  [0], // t06
417  [1,1,1,1,1,1,0], // t07
418  [1,1,0,0,1], // t08
419  [1,0,0,0,0,0,0,0,0,0,0], // t09
420  [1,0,0,0,0,1,0,0,1,1,1,0,1], // t10
421  [1,1,0,1,0,0,0,0,1,1], // t11
422  [1,1,0,1,0,1,1,0,0,0] // t12
423  ],
424  ["binary_i2v_v2i", 1,
425  0, // t01
426  0, // t02
427  254, // t03
428  254, // t04
429  255, // t05
430  0, // t06
431  126, // t07
432  25, // t08
433  1024, // t09
434  4253, // t10
435  835, // t11
436  856 // t12
437  ],
438  ["binary_i2s", 1,
439  undef, // t01
440  undef, // t02
441  "11111110", // t03
442  "11111110", // t04
443  "11111111", // t05
444  "0", // t06
445  "1111110", // t07
446  "11001", // t08
447  "10000000000", // t09
448  "1000010011101", // t10
449  "1101000011", // t11
450  "1101011000" // t12
451  ],
452  ["binary_i2s_s2i", 1,
453  0, // t01
454  0, // t02
455  254, // t03
456  254, // t04
457  255, // t05
458  0, // t06
459  126, // t07
460  25, // t08
461  1024, // t09
462  4253, // t10
463  835, // t11
464  856 // t12
465  ],
466  ["binary_iw2i_32", 1,
467  undef, // t01
468  undef, // t02
469  7, // t03
470  7, // t04
471  7, // t05
472  0, // t06
473  7, // t07
474  6, // t08
475  0, // t09
476  7, // t10
477  0, // t11
478  6 // t12
479  ],
480  ["binary_and", 2,
481  undef, // t01
482  undef, // t02
483  0, // t03
484  0, // t04
485  0, // t05
486  0, // t06
487  62, // t07
488  8, // t08
489  0, // t09
490  25, // t10
491  769, // t11
492  592 // t12
493  ],
494  ["binary_or", 2,
495  undef, // t01
496  undef, // t02
497  254, // t03
498  255, // t04
499  255, // t05
500  255, // t06
501  127, // t07
502  27, // t08
503  1536, // t09
504  4543, // t10
505  835, // t11
506  889 // t12
507  ],
508  ["binary_xor", 2,
509  undef, // t01
510  undef, // t02
511  254, // t03
512  255, // t04
513  255, // t05
514  255, // t06
515  65, // t07
516  19, // t08
517  1536, // t09
518  4518, // t10
519  66, // t11
520  297 // t12
521  ],
522  ["binary_not", 1,
523  undef, // t01
524  undef, // t02
525  1, // t03
526  1, // t04
527  0, // t05
528  1, // t06
529  1, // t07
530  6, // t08
531  1023, // t09
532  3938, // t10
533  188, // t11
534  167 // t12
535  ],
536  ["binary_ishl", 1,
537  undef, // t01
538  undef, // t02
539  508, // t03
540  508, // t04
541  510, // t05
542  0, // t06
543  252, // t07
544  50, // t08
545  2048, // t09
546  8506, // t10
547  1670, // t11
548  1712 // t12
549  ],
550  ["binary_ishr", 1,
551  undef, // t01
552  undef, // t02
553  127, // t03
554  127, // t04
555  127, // t05
556  0, // t06
557  63, // t07
558  12, // t08
559  512, // t09
560  2126, // t10
561  417, // t11
562  428 // t12
563  ]
564  ];
565 
566  // sanity-test tables
567  table_check( test_r, test_c, false );
568  table_check( good_r, good_c, false );
569 
570  // validate helper function and module
571  function get_value( vid ) = table_get_value(test_r, test_c, vid, "tv");
572  function gv( vid, e ) = get_value( vid )[e];
573  module log_test( m ) { log_type ( "test", m ); }
574  module log_skip( f ) { log_test ( str("ignore: '", f, "'") ); }
575  module run( fname, vid )
576  {
577  value_text = table_get_value(test_r, test_c, vid, "td");
578 
579  if ( table_get_value(good_r, good_c, fname, vid) != skip )
580  children();
581  else
582  log_test( str(vid, " -skip-: '", fname, "(", value_text, ")'") );
583  }
584  module test( fname, fresult, vid )
585  {
586  value_text = table_get_value(test_r, test_c, vid, "td");
587  fname_argc = table_get_value(good_r, good_c, fname, "fac");
588  pass_value = table_get_value(good_r, good_c, fname, vid);
589 
590  test_pass = validate(cv=fresult, t="equals", ev=pass_value, pf=true);
591  farg_text = strl(append_e(", ", select_r(get_value(vid), [0:fname_argc-1]), r=false, j=false, l=false));
592  test_text = validate(str(fname, "(", farg_text, ")=", pass_value), fresult, "equals", pass_value);
593 
594  if ( pass_value != skip )
595  {
596  if ( !test_pass )
597  log_test( str(vid, " ", test_text, " (", value_text, ")") );
598  else
599  log_test( str(vid, " ", test_text) );
600  }
601  else
602  log_test( str(vid, " -skip-: '", fname, "(", value_text, ")'") );
603  }
604 
605  // Indirect function calls would be very useful here!!!
606  run_ids = delete( test_ids, mv=["fac", "crp"] );
607  for (vid=run_ids) run("binary_bit_is_0",vid) test( "binary_bit_is_0", binary_bit_is(gv(vid,0),gv(vid,1),0), vid );
608  for (vid=run_ids) run("binary_bit_is_1",vid) test( "binary_bit_is_1", binary_bit_is(gv(vid,0),gv(vid,1),1), vid );
609  for (vid=run_ids) run("binary_i2v",vid) test( "binary_i2v", binary_i2v(gv(vid,0)), vid );
610  for (vid=run_ids) run("binary_i2v_v2i",vid) test( "binary_i2v_v2i", binary_v2i(binary_i2v(gv(vid,0))), vid );
611  for (vid=run_ids) run("binary_i2s",vid) test( "binary_i2s", binary_i2s(gv(vid,0)), vid );
612  for (vid=run_ids) run("binary_i2s_s2i",vid) test( "binary_i2s_s2i", binary_s2i(binary_i2s(gv(vid,0))), vid );
613  for (vid=run_ids) run("binary_iw2i_32",vid) test( "binary_iw2i_32", binary_iw2i(gv(vid,0),2,3), vid );
614  for (vid=run_ids) run("binary_and",vid) test( "binary_and", binary_and(gv(vid,0),gv(vid,1)), vid );
615  for (vid=run_ids) run("binary_or",vid) test( "binary_or", binary_or(gv(vid,0),gv(vid,1)), vid );
616  for (vid=run_ids) run("binary_xor",vid) test( "binary_xor", binary_xor(gv(vid,0),gv(vid,1)), vid );
617  for (vid=run_ids) run("binary_not",vid) test( "binary_not", binary_not(gv(vid,0)), vid );
618  for (vid=run_ids) run("binary_ishl",vid) test( "binary_ishl", binary_ishl(gv(vid,0)), vid );
619  for (vid=run_ids) run("binary_ishr",vid) test( "binary_ishr", binary_ishr(gv(vid,0)), vid );
620 
621  // end_include
622  END_OPENSCAD;
623 
624  BEGIN_MFSCRIPT;
625  include --path "${INCLUDE_PATH}" {var_init,var_gen_term}.mfs;
626  include --path "${INCLUDE_PATH}" scr_make_mf.mfs;
627  END_MFSCRIPT;
628 END_SCOPE;
629 */
630 
631 //----------------------------------------------------------------------------//
632 // end of file
633 //----------------------------------------------------------------------------//
empty_lst
empty_lst
<list> A list with no values (the empty list).
Definition: constants.scad:304
binary_iw2i
function binary_iw2i(v, s, w)
Decode the binary bits of a bit window to an integer value.
binary_xor
function binary_xor(v1, v2, _bv=1)
Base-2 binary XOR operation for integers.
binary_ishl
function binary_ishl(v, s=1)
Base-2 binary left-shift operation for an integer.
binary_i2s
function binary_i2s(v, w=1)
Encode an integer value as a binary string of bits.
binary_not
function binary_not(v, w=1, _bv=1)
Base-2 binary NOT operation for an integer.
binary_and
function binary_and(v1, v2, _bv=1)
Base-2 binary AND operation for integers.
binary_bit_is
function binary_bit_is(v, b, t=1)
Test if a binary bit position of an integer value equals a test bit.
binary_v2i
function binary_v2i(v)
Decode a binary list of bits to an integer value.
binary_ishr
function binary_ishr(v, s=1)
Base-2 binary right-shift operation for an integer.
binary_i2v
function binary_i2v(v, w=1, _bv=1)
Encode an integer value as a binary list of bits.
binary_or
function binary_or(v1, v2, _bv=1)
Base-2 binary OR operation for integers.
binary_s2i
function binary_s2i(v)
Decode a binary string of bits to an integer value.
first
function first(v)
Return the first element of an iterable value.
tailn
function tailn(v, n=1)
Return a list containing all but the first n elements of an iterable value.
is_empty
function is_empty(v)
Test if an iterable value is empty.
all_oneof
function all_oneof(v, cv)
Test if all elements of an iterable value equal one of the comparison values.
strl
function strl(v)
Convert a list of values to a concatenated string.
is_integer
function is_integer(v)
Test if a value is an integer.