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