basis/math/bitwise/bitwise-docs.factor

   1 ! Copyright (C) 2008 Doug Coleman.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: assocs help.markup help.syntax math sequences kernel ;
   4 IN: math.bitwise
   5
   6 HELP: bitfield
   7 { $values { "values..." "a series of objects on the stack" } { "bitspec" "an array" } { "n" integer } }
   8     { $description "Constructs an integer (bit field) from a series of values on the stack together with a bit field specifier, which is an array whose elements have one of the following shapes:"
   9     { $list
  10         { { $snippet "{ word shift }" } " - " { $snippet "word" } " is applied to the top of the stack and the result is shifted to the left by " { $snippet "shift" } " bits and bitor'd with the bit field" }
  11         { { $snippet "shift" } " - the top of the stack is shifted to the left by " { $snippet "shift" } " bits and bitor'd with the bit field" }
  12         { { $snippet "{ constant shift }" } " - " { $snippet "constant" } " is shifted to the left by " { $snippet "shift" } " bits and bitor'd with the bit field" }
  13     }
  14     "The last entry in the bit field specifier is processed in reverse, so stack values are supplied in reverse order, e.g. the leftmost stack value is the last bit field specifier."
  15 }
  16 { $examples
  17     "Consider the following specification:"
  18     { $list
  19         { "bits 0-10 are set to the value of " { $snippet "x" } }
  20         { "bits 11-14 are set to the value of " { $snippet "y" } }
  21         { "bit 15 is always on" }
  22         { "bits 16-20 are set to the value of " { $snippet "fooify" } " applied to " { $snippet "z" } }
  23     }
  24     "Such a bit field construction can be specified with a word like the following:"
  25     { $example
  26         "USING: math math.bitwise prettyprint ;"
  27         "IN: math.bitwise.examples"
  28         ": fooify ( x -- y ) 0b1111 bitand ;"
  29         ": baz-bitfield ( x y z -- n )"
  30         "    {"
  31         "        { fooify 16 }"
  32         "        { 1 15 }"
  33         "        11"
  34         "        0"
  35         "    } bitfield ;"
  36         "3 2 1 baz-bitfield ."
  37         "102403"
  38     }
  39     "Square the 3 from the stack and shift 8, place the 1 from the stack at bit 5, and shift a constant 1 to bit 2:"
  40     { $example
  41         "USING: math math.bitwise prettyprint ;"
  42         "1 3"
  43         "    {"
  44         "        { sq 8 }"
  45         "        5"
  46         "        { 1 2 }"
  47         "    } bitfield .b"
  48         "0b100100100100"
  49     }
  50 } ;
  51
  52 HELP: bitfield*
  53 { $values { "values..." "a series of objects on the stack" } { "bitspec" "an array" } { "n" integer } }
  54 { $description "Constructs an integer (bit field) from a series of values on the stack together with a bit field specifier, which is an array whose elements have one of the following shapes:"
  55     { $list
  56         { { $snippet "{ word shift }" } " - " { $snippet "word" } " is applied to the top of the stack and the result is shifted to the left by " { $snippet "shift" } " bits and bitor'd with the bit field" }
  57         { { $snippet "shift" } " - the top of the stack is shifted to the left by " { $snippet "shift" } " bits and bitor'd with the bit field" }
  58         { { $snippet "{ constant shift }" } " - " { $snippet "constant" } " is shifted to the left by " { $snippet "shift" } " bits and bitor'd with the bit field" }
  59     }
  60     "The bit field specifier is processed in order, so stack values are taken from left to right."
  61 }
  62 { $examples
  63     "Consider the following specification:"
  64     { $list
  65         { "bits 0-10 are set to the value of " { $snippet "x" } }
  66         { "bits 11-14 are set to the value of " { $snippet "y" } }
  67         { "bit 15 is always on" }
  68         { "bits 16-20 are set to the value of " { $snippet "fooify" } " applied to " { $snippet "z" } }
  69     }
  70     "Such a bit field construction can be specified with a word like the following:"
  71     { $example
  72         "USING: math math.bitwise prettyprint ;"
  73         "IN: math.bitwise.examples"
  74         ": fooify ( x -- y ) 0b1111 bitand ;"
  75         ": baz-bitfield* ( x y z -- n )"
  76         "    {"
  77         "        0"
  78         "        11"
  79         "        { 1 15 }"
  80         "        { fooify 16 }"
  81         "    } bitfield* ;"
  82         "1 2 3 baz-bitfield* ."
  83         "233473"
  84     }
  85     "Put a 1 at bit 1, put the 1 from the stack at bit 5, square the 3 and put it at bit 8:"
  86     { $example
  87         "USING: math math.bitwise prettyprint ;"
  88         "1 3"
  89         "    {"
  90         "        { 1 2 }"
  91         "        5"
  92         "        { sq 8 }"
  93         "    } bitfield* .b"
  94         "0b100100100100"
  95     }
  96 } ;
  97
  98 { bitfield bitfield* } related-words
  99
 100 HELP: bits
 101 { $values { "m" integer } { "n" integer } { "m'" integer } }
 102 { $description "Keep only " { $snippet "n" } " bits from the integer " { $snippet "m" } ". For negative numbers, represent the number as two's complement (a positive integer representing a negative integer)." }
 103 { $examples
 104     { $example
 105         "USING: math.bitwise prettyprint ;"
 106         "0x123abcdef 16 bits .h"
 107         "0xcdef"
 108     }
 109     { $example
 110         "USING: math.bitwise prettyprint ;"
 111         "-2 16 bits .h"
 112         "0xfffe"
 113     }
 114 } ;
 115
 116 HELP: bit-range
 117 { $values { "x" integer } { "high" integer } { "low" integer } { "y" integer } }
 118 { $description "Extract a range of bits from an integer, inclusive of each boundary." }
 119 { $example "USING: math.bitwise prettyprint ;" "0b1100 3 2 bit-range .b" "0b11" } ;
 120
 121 HELP: bitroll
 122 { $values { "x" integer } { "s" "a shift integer" } { "w" "a wrap integer" } { "y" integer }
 123 }
 124 { $description "Roll " { $snippet "n" } " by " { $snippet "s" } " bits to the left, wrapping around after " { $snippet "w" } " bits." }
 125 { $examples
 126     { $example "USING: math.bitwise prettyprint ;" "1 -1 32 bitroll .b" "0b10000000000000000000000000000000" }
 127     { $example "USING: math.bitwise prettyprint ;" "0xffff0000 8 32 bitroll .h" "0xff0000ff" }
 128 } ;
 129
 130 { bit? set-bit clear-bit } related-words
 131
 132 HELP: bit-count
 133 { $values
 134      { "obj" object }
 135      { "n" integer }
 136 }
 137 { $description "Returns the number of set bits as an object. This word only works on non-negative integers or objects that can be represented as a byte-array." }
 138 { $examples
 139     { $example "USING: math.bitwise prettyprint ;"
 140                "0xf0 bit-count ."
 141                "4"
 142     }
 143     { $example "USING: math.bitwise prettyprint ;"
 144                "-1 32 bits bit-count ."
 145                "32"
 146     }
 147     { $example "USING: math.bitwise prettyprint ;"
 148                "B{ 1 0 1 } bit-count ."
 149                "2"
 150     }
 151 } ;
 152
 153 HELP: bitroll-32
 154 { $values
 155      { "m" integer } { "s" integer }
 156      { "n" integer }
 157 }
 158 { $description "Rolls the number " { $snippet "m" } " by " { $snippet "s" } " bits to the left, wrapping around after 32 bits." }
 159 { $examples
 160     { $example "USING: math.bitwise prettyprint ;"
 161                "0x1 10 bitroll-32 .h"
 162                "0x400"
 163     }
 164     { $example "USING: math.bitwise prettyprint ;"
 165                "0x1 -10 bitroll-32 .h"
 166                "0x400000"
 167     }
 168 } ;
 169
 170 HELP: bitroll-64
 171 { $values
 172      { "m" integer } { "s" "a shift integer" }
 173      { "n" integer }
 174 }
 175 { $description "Rolls the number " { $snippet "m" } " by " { $snippet "s" } " bits to the left, wrapping around after 64 bits." }
 176 { $examples
 177     { $example "USING: math.bitwise prettyprint ;"
 178                "0x1 10 bitroll-64 .h"
 179                "0x400"
 180     }
 181     { $example "USING: math.bitwise prettyprint ;"
 182                "0x1 -10 bitroll-64 .h"
 183                "0x40000000000000"
 184     }
 185 } ;
 186
 187 { bitroll bitroll-32 bitroll-64 } related-words
 188
 189 HELP: clear-bit
 190 { $values
 191      { "x" integer } { "n" integer }
 192      { "y" integer }
 193 }
 194 { $description "Sets the " { $snippet "n" } "th bit of " { $snippet "x" } " to zero." }
 195 { $examples
 196     { $example "USING: math.bitwise kernel prettyprint ;"
 197         "0xff 7 clear-bit .h"
 198         "0x7f"
 199     }
 200 } ;
 201
 202 HELP: symbols>flags
 203 { $values { "symbols" sequence } { "assoc" assoc } { "flag-bits" integer } }
 204 { $description "Constructs an integer value by mapping the values in the " { $snippet "symbols" } " sequence to integer values using " { $snippet "assoc" } " and " { $link bitor } "ing the values together." }
 205 { $examples
 206     { $example "USING: math.bitwise prettyprint ui.gadgets.worlds ;"
 207         "IN: scratchpad"
 208         "CONSTANT: window-controls>flags H{"
 209         "    { close-button 1 }"
 210         "    { minimize-button 2 }"
 211         "    { maximize-button 4 }"
 212         "    { resize-handles 8 }"
 213         "    { small-title-bar 16 }"
 214         "    { normal-title-bar 32 }"
 215         "}"
 216         "{ resize-handles close-button small-title-bar } window-controls>flags symbols>flags ."
 217         "25"
 218     }
 219 } ;
 220
 221 HELP: >even
 222 { $values
 223     { "m" integer }
 224     { "n" integer }
 225 }
 226 { $examples
 227     { $example "USING: math.bitwise prettyprint ;"
 228         "7 >even ."
 229         "6"
 230     }
 231 }
 232 { $description "Sets the lowest bit in the integer to 0, which either does nothing or outputs 1 less than the input integer." } ;
 233
 234 HELP: >odd
 235 { $values
 236     { "m" integer }
 237     { "n" integer }
 238 }
 239 { $examples
 240     { $example "USING: math.bitwise prettyprint ;"
 241         "4 >odd ."
 242         "5"
 243     }
 244 }
 245 { $description "Sets the lowest bit in the integer to 1, which either does nothing or outputs 1 more than the input integer." } ;
 246
 247 HELP: >signed
 248 { $values
 249     { "x" integer } { "n" integer }
 250     { "y" integer }
 251 }
 252 { $examples
 253     { $example "USING: math.bitwise prettyprint ;"
 254         "0xff 8 >signed ."
 255         "-1"
 256     }
 257     { $example "USING: math.bitwise prettyprint ;"
 258         "0xf0 4 >signed ."
 259         "0"
 260     }
 261 }
 262 { $description "Interprets a number " { $snippet "x" } " as an " { $snippet "n" } "-bit number and converts it to a negative number if the topmost bit is set." } ;
 263
 264 { >signed bits } related-words
 265
 266 HELP: mask
 267 { $values
 268      { "x" integer } { "n" integer }
 269      { "y" integer }
 270 }
 271 { $description "After the operation, only the bits that were set in both the mask and the original number are set." }
 272 { $examples
 273     { $example "USING: math.bitwise kernel prettyprint ;"
 274         "0b11111111 0b101 mask .b"
 275         "0b101"
 276     }
 277 } ;
 278
 279 HELP: mask-bit
 280 { $values
 281      { "m" integer } { "n" integer }
 282      { "m'" integer }
 283 }
 284 { $description "Turns off all bits besides the " { $snippet "n" } "th bit." }
 285 { $examples
 286     { $example "USING: math.bitwise kernel prettyprint ;"
 287         "0xff 2 mask-bit .b"
 288         "0b100"
 289     }
 290 } ;
 291
 292 HELP: mask?
 293 { $values
 294      { "x" integer } { "n" integer }
 295      { "?" boolean }
 296 }
 297 { $description "Returns true if all of the bits in the mask " { $snippet "n" } " are set in the integer input " { $snippet "x" } "." }
 298 { $examples
 299     { $example "USING: math.bitwise kernel prettyprint ;"
 300         "0xff 0xf mask? ."
 301         "t"
 302     }
 303
 304     { $example "USING: math.bitwise kernel prettyprint ;"
 305         "0xf0 0x1 mask? ."
 306         "f"
 307     }
 308 } ;
 309
 310 HELP: even-parity?
 311 { $values
 312     { "obj" object }
 313     { "?" boolean }
 314 }
 315 { $description "Returns true if the number of set bits in an object is even." } ;
 316
 317 HELP: odd-parity?
 318 { $values
 319     { "obj" object }
 320     { "?" boolean }
 321 }
 322 { $description "Returns true if the number of set bits in an object is odd." } ;
 323
 324 HELP: on-bits
 325 { $values
 326      { "m" integer }
 327      { "n" integer }
 328 }
 329 { $description "Returns an integer with " { $snippet "m" } " bits set." }
 330 { $examples
 331     { $example "USING: math.bitwise kernel prettyprint ;"
 332         "6 on-bits .h"
 333         "0x3f"
 334     }
 335     { $example "USING: math.bitwise kernel prettyprint ;"
 336         "64 on-bits .h"
 337         "0xffffffffffffffff"
 338     }
 339 } ;
 340
 341 HELP: toggle-bit
 342 { $values
 343      { "m" integer }
 344      { "n" integer }
 345      { "m'" integer }
 346 }
 347 { $description "Toggles the " { $snippet "n" } "th bit of an integer." }
 348 { $examples
 349     { $example "USING: math.bitwise kernel prettyprint ;"
 350         "0 3 toggle-bit .b"
 351         "0b1000"
 352     }
 353     { $example "USING: math.bitwise kernel prettyprint ;"
 354         "0b1000 3 toggle-bit .b"
 355         "0b0"
 356     }
 357 } ;
 358
 359 HELP: set-bit
 360 { $values
 361      { "x" integer } { "n" integer }
 362      { "y" integer }
 363 }
 364 { $description "Sets the " { $snippet "n" } "th bit of " { $snippet "x" } "." }
 365 { $examples
 366     { $example "USING: math.bitwise kernel prettyprint ;"
 367         "0 5 set-bit .h"
 368         "0x20"
 369     }
 370 } ;
 371
 372 HELP: shift-mod
 373 { $values
 374      { "m" integer } { "s" integer } { "w" integer }
 375      { "n" integer }
 376 }
 377 { $description "Calls " { $link shift } " on " { $snippet "n" } " and " { $snippet "s" } ", wrapping the result to " { $snippet "w" } " bits." } ;
 378
 379 HELP: unmask
 380 { $values
 381      { "x" integer } { "n" integer }
 382      { "y" integer }
 383 }
 384 { $description "Clears the bits in " { $snippet "x" } " if they are set in the mask " { $snippet "n" } "." }
 385 { $examples
 386     { $example "USING: math.bitwise kernel prettyprint ;"
 387         "0xff 0x0f unmask .h"
 388         "0xf0"
 389     }
 390 } ;
 391
 392 HELP: unmask?
 393 { $values
 394      { "x" integer } { "n" integer }
 395      { "?" boolean }
 396 }
 397 { $description "Tests whether unmasking the bits in " { $snippet "x" } " would return an integer greater than zero." }
 398 { $examples
 399     { $example "USING: math.bitwise kernel prettyprint ;"
 400         "0xff 0x0f unmask? ."
 401         "t"
 402     }
 403 } ;
 404
 405 HELP: w*
 406 { $values
 407      { "x" integer } { "y" integer }
 408      { "z" integer }
 409 }
 410 { $description "Multiplies two integers and wraps the result to a 32-bit unsigned integer." }
 411 { $examples
 412     { $example "USING: math.bitwise kernel prettyprint ;"
 413         "0xffffffff 0x2 w* ."
 414         "4294967294"
 415     }
 416 } ;
 417
 418 HELP: w+
 419 { $values
 420      { "x" integer } { "y" integer }
 421      { "z" integer }
 422 }
 423 { $description "Adds two integers and wraps the result to a 32-bit unsigned integer." }
 424 { $examples
 425     { $example "USING: math.bitwise kernel prettyprint ;"
 426         "0xffffffff 0x2 w+ ."
 427         "1"
 428     }
 429 } ;
 430
 431 HELP: w-
 432 { $values
 433      { "x" integer } { "y" integer }
 434      { "z" integer }
 435 }
 436 { $description "Subtracts two integers and wraps the result to a 32-bit unsigned integer." }
 437 { $examples
 438     { $example "USING: math.bitwise kernel prettyprint ;"
 439         "0x0 0xff w- ."
 440         "4294967041"
 441     }
 442 } ;
 443
 444 HELP: W*
 445 { $values
 446      { "x" integer } { "y" integer }
 447      { "z" integer }
 448 }
 449 { $description "Multiplies two integers and wraps the result to a 64-bit unsigned integer." }
 450 { $examples
 451     { $example "USING: math.bitwise kernel prettyprint ;"
 452         "0xffffffffffffffff 0x2 W* ."
 453         "18446744073709551614"
 454     }
 455 } ;
 456
 457 HELP: W+
 458 { $values
 459      { "x" integer } { "y" integer }
 460      { "z" integer }
 461 }
 462 { $description "Adds two integers and wraps the result to 64-bit unsigned integer." }
 463 { $examples
 464     { $example "USING: math.bitwise kernel prettyprint ;"
 465         "0xffffffffffffffff 0x2 W+ ."
 466         "1"
 467     }
 468 } ;
 469
 470 HELP: W-
 471 { $values
 472      { "x" integer } { "y" integer }
 473      { "z" integer }
 474 }
 475 { $description "Subtracts two integers and wraps the result to a 64-bit unsigned integer." }
 476 { $examples
 477     { $example "USING: math.bitwise kernel prettyprint ;"
 478         "0x0 0xff W- ."
 479         "18446744073709551361"
 480     }
 481 } ;
 482
 483 HELP: wrap
 484 { $values
 485      { "m" integer } { "n" integer }
 486      { "m'" integer }
 487 }
 488 { $description "Wraps an integer " { $snippet "m" } " by modding it by " { $snippet "n" } ". This word is uses bitwise arithmetic and does not actually call the modulus word, and as such can only mod by powers of two." }
 489 { $examples "Equivalent to modding by 8:"
 490     { $example
 491         "USING: math.bitwise prettyprint ;"
 492         "0xffff 8 wrap .h"
 493         "0x7"
 494     }
 495 } ;
 496
 497 ARTICLE: "math-bitfields" "Constructing bit fields"
 498 "Some applications, such as binary communication protocols and assemblers, need to construct integers from elaborate bit field specifications. Hand-coding this using " { $link shift } " and " { $link bitor } " results in repetitive code. A higher-level facility exists to factor out this repetition:"
 499 { $subsections bitfield } ;
 500
 501 ARTICLE: "math.bitwise" "Additional bitwise arithmetic"
 502 "The " { $vocab-link "math.bitwise" } " vocabulary provides bitwise arithmetic words extending " { $link "bitwise-arithmetic" } ". They are useful for efficiency, low-level programming, and interfacing with C libraries."
 503 $nl
 504 "Setting and clearing bits:"
 505 { $subsections
 506     set-bit
 507     clear-bit
 508 }
 509 "Testing if bits are set:"
 510 { $subsections
 511     bit?
 512 }
 513 "Extracting bits from an integer:"
 514 { $subsections
 515     bit-range
 516     bits
 517 }
 518 "Toggling a bit:"
 519 { $subsections
 520     toggle-bit
 521 }
 522 "Operations with bitmasks:"
 523 { $subsections
 524     mask
 525     unmask
 526     mask?
 527     unmask?
 528 }
 529 "Generating an integer with n set bits:"
 530 { $subsections on-bits }
 531 "Counting the number of set bits:"
 532 { $subsections bit-count }
 533 "Testing the parity of an object:"
 534 { $subsections even-parity? odd-parity? }
 535 "More efficient modding by powers of two:"
 536 { $subsections wrap }
 537 "Bit-rolling:"
 538 { $subsections
 539     bitroll
 540     bitroll-32
 541     bitroll-64
 542 }
 543 "32-bit arithmetic:"
 544 { $subsections
 545     w+
 546     w-
 547     w*
 548 }
 549 "64-bit arithmetic:"
 550 { $subsections
 551     W+
 552     W-
 553     W*
 554 }
 555 "Converting a number to the nearest even/odd/signed:"
 556 { $subsections
 557     >even
 558     >odd
 559     >signed
 560 }
 561 "Bitfields:"
 562 { $subsections
 563     "math-bitfields"
 564 } ;
 565
 566 ABOUT: "math.bitwise"