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" } { "bitspec" "an array" } { "n" integer } }
   8 { $description "Constructs an integer 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 "{ constant shift }" } " - the resulting bit field is bitwise or'd with " { $snippet "constant" } " shifted to the right by " { $snippet "shift" } " bits" }
  11         { { $snippet "{ word shift }" } " - the resulting bit field is bitwise or'd with " { $snippet "word" } " applied to the top of the stack; the result is shifted to the right by " { $snippet "shift" } " bits" }
  12         { { $snippet "shift" } " - the resulting bit field is bitwise or'd with the top of the stack; the result is shifted to the right by " { $snippet "shift" } " bits" }
  13     }
  14 "The bit field specifier is processed left to right, so stack values should be supplied in reverse order." }
  15 { $examples
  16     "Consider the following specification:"
  17     { $list
  18         { "bits 0-10 are set to the value of " { $snippet "x" } }
  19         { "bits 11-14 are set to the value of " { $snippet "y" } }
  20         { "bit 15 is always on" }
  21         { "bits 16-20 are set to the value of " { $snippet "fooify" } " applied to " { $snippet "z" } }
  22     }
  23     "Such a bit field construction can be specified with a word like the following:"
  24     { $code
  25         ": baz-bitfield ( x y z -- n )"
  26         "    {"
  27         "        { fooify 16 }"
  28         "        { 1 15 }"
  29         "        11"
  30         "        0"
  31         "    } ;"
  32     }
  33 } ;
  34
  35 HELP: bits
  36 { $values { "m" integer } { "n" integer } { "m'" integer } }
  37 { $description "Keep only n bits from the integer m." }
  38 { $example "USING: math.bitwise prettyprint ;" "0x123abcdef 16 bits .h" "cdef" } ;
  39
  40 HELP: bitroll
  41 { $values { "x" integer } { "s" "a shift integer" } { "w" "a wrap integer" } { "y" integer }
  42 }
  43 { $description "Roll n by s bits to the left, wrapping around after w bits." }
  44 { $examples
  45     { $example "USING: math.bitwise prettyprint ;" "1 -1 32 bitroll .b" "10000000000000000000000000000000" }
  46     { $example "USING: math.bitwise prettyprint ;" "0xffff0000 8 32 bitroll .h" "ff0000ff" }
  47 } ;
  48
  49 HELP: bit-clear?
  50 { $values
  51      { "x" integer } { "n" integer }
  52      { "?" "a boolean" }
  53 }
  54 { $description "Returns " { $link t } " if the nth bit is set to zero." }
  55 { $examples
  56     { $example "USING: math.bitwise prettyprint ;"
  57                "0xff 8 bit-clear? ."
  58                "t"
  59     }
  60     { $example "USING: math.bitwise prettyprint ;"
  61                "0xff 7 bit-clear? ."
  62                "f"
  63     }
  64 } ;
  65
  66 { bit? bit-clear? set-bit clear-bit } related-words
  67
  68 HELP: bit-count
  69 { $values
  70      { "obj" object }
  71      { "n" integer }
  72 }
  73 { $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." }
  74 { $examples
  75     { $example "USING: math.bitwise prettyprint ;"
  76                "0xf0 bit-count ."
  77                "4"
  78     }
  79     { $example "USING: math.bitwise prettyprint ;"
  80                "-1 32 bits bit-count ."
  81                "32"
  82     }
  83     { $example "USING: math.bitwise prettyprint ;"
  84                "B{ 1 0 1 } bit-count ."
  85                "2"
  86     }
  87 } ;
  88
  89 HELP: bitroll-32
  90 { $values
  91      { "m" integer } { "s" integer }
  92      { "n" integer }
  93 }
  94 { $description "Rolls the number " { $snippet "m" } " by " { $snippet "s" } " bits to the left, wrapping around after 32 bits." }
  95 { $examples
  96     { $example "USING: math.bitwise prettyprint ;"
  97                "0x1 10 bitroll-32 .h"
  98                "400"
  99     }
 100     { $example "USING: math.bitwise prettyprint ;"
 101                "0x1 -10 bitroll-32 .h"
 102                "400000"
 103     }
 104 } ;
 105
 106 HELP: bitroll-64
 107 { $values
 108      { "m" integer } { "s" "a shift integer" }
 109      { "n" integer }
 110 }
 111 { $description "Rolls the number " { $snippet "m" } " by " { $snippet "s" } " bits to the left, wrapping around after 64 bits." }
 112 { $examples
 113     { $example "USING: math.bitwise prettyprint ;"
 114                "0x1 10 bitroll-64 .h"
 115                "400"
 116     }
 117     { $example "USING: math.bitwise prettyprint ;"
 118                "0x1 -10 bitroll-64 .h"
 119                "40000000000000"
 120     }
 121 } ;
 122
 123 { bitroll bitroll-32 bitroll-64 } related-words
 124
 125 HELP: clear-bit
 126 { $values
 127      { "x" integer } { "n" integer }
 128      { "y" integer }
 129 }
 130 { $description "Sets the nth bit of " { $snippet "x" } " to zero." }
 131 { $examples
 132     { $example "USING: math.bitwise kernel prettyprint ;"
 133         "0xff 7 clear-bit .h"
 134         "7f"
 135     }
 136 } ;
 137
 138 HELP: symbols>flags
 139 { $values { "symbols" sequence } { "assoc" assoc } { "flag-bits" integer } }
 140 { $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." }
 141 { $examples
 142     { $example "USING: math.bitwise prettyprint ui.gadgets.worlds ;"
 143         "IN: scratchpad"
 144         "CONSTANT: window-controls>flags H{"
 145         "    { close-button 1 }"
 146         "    { minimize-button 2 }"
 147         "    { maximize-button 4 }"
 148         "    { resize-handles 8 }"
 149         "    { small-title-bar 16 }"
 150         "    { normal-title-bar 32 }"
 151         "}"
 152         "{ resize-handles close-button small-title-bar } window-controls>flags symbols>flags ."
 153         "25"
 154     }
 155 } ;
 156
 157 HELP: >even
 158 { $values
 159     { "m" integer }
 160     { "n" integer }
 161 }
 162 { $examples
 163     { $example "USING: math.bitwise prettyprint ;"
 164         "7 >even ."
 165         "6"
 166     }
 167 }
 168 { $description "Sets the lowest bit in the integer to 0, which either does nothing or outputs 1 less than the input integer." } ;
 169
 170 HELP: >odd
 171 { $values
 172     { "m" integer }
 173     { "n" integer }
 174 }
 175 { $examples
 176     { $example "USING: math.bitwise prettyprint ;"
 177         "4 >odd ."
 178         "5"
 179     }
 180 }
 181 { $description "Sets the lowest bit in the integer to 1, which either does nothing or outputs 1 more than the input integer." } ;
 182
 183 HELP: >signed
 184 { $values
 185     { "x" integer } { "n" integer }
 186     { "y" integer }
 187 }
 188 { $examples
 189     { $example "USING: math.bitwise prettyprint ;"
 190         "0xff 8 >signed ."
 191         "-1"
 192     }
 193 }
 194 { $description "Interprets a number " { $snippet "x" } " as an " { $snippet "n" } "-bit number and converts it to a negative number " { $snippet "n" } "-bit number if the topmost bit is set." } ;
 195
 196 HELP: mask
 197 { $values
 198      { "x" integer } { "n" integer }
 199      { "?" "a boolean" }
 200 }
 201 { $description "After the operation, only the bits that were set in both the mask and the original number are set." }
 202 { $examples
 203     { $example "USING: math.bitwise kernel prettyprint ;"
 204         "0b11111111 0b101 mask .b"
 205         "101"
 206     }
 207 } ;
 208
 209 HELP: mask-bit
 210 { $values
 211      { "m" integer } { "n" integer }
 212      { "m'" integer }
 213 }
 214 { $description "Turns off all bits besides the nth bit." }
 215 { $examples
 216     { $example "USING: math.bitwise kernel prettyprint ;"
 217         "0xff 2 mask-bit .b"
 218         "100"
 219     }
 220 } ;
 221
 222 HELP: mask?
 223 { $values
 224      { "x" integer } { "n" integer }
 225      { "?" "a boolean" }
 226 }
 227 { $description "Returns true if all of the bits in the mask " { $snippet "n" } " are set in the integer input " { $snippet "x" } "." }
 228 { $examples
 229     { $example "USING: math.bitwise kernel prettyprint ;"
 230         "0xff 0xf mask? ."
 231         "t"
 232     }
 233
 234     { $example "USING: math.bitwise kernel prettyprint ;"
 235         "0xf0 0x1 mask? ."
 236         "f"
 237     }
 238 } ;
 239
 240 HELP: even-parity?
 241 { $values
 242     { "obj" object }
 243     { "?" boolean }
 244 }
 245 { $description "Returns true if the number of set bits in an object is even." } ;
 246
 247 HELP: odd-parity?
 248 { $values
 249     { "obj" object }
 250     { "?" boolean }
 251 }
 252 { $description "Returns true if the number of set bits in an object is odd." } ;
 253
 254 HELP: on-bits
 255 { $values
 256      { "m" integer }
 257      { "n" integer }
 258 }
 259 { $description "Returns an integer with " { $snippet "m" } " bits set." }
 260 { $examples
 261     { $example "USING: math.bitwise kernel prettyprint ;"
 262         "6 on-bits .h"
 263         "3f"
 264     }
 265     { $example "USING: math.bitwise kernel prettyprint ;"
 266         "64 on-bits .h"
 267         "ffffffffffffffff"
 268     }
 269 } ;
 270
 271 HELP: toggle-bit
 272 { $values
 273      { "m" integer }
 274      { "n" integer }
 275      { "m'" integer }
 276 }
 277 { $description "Toggles the nth bit of an integer." }
 278 { $examples
 279     { $example "USING: math.bitwise kernel prettyprint ;"
 280         "0 3 toggle-bit .b"
 281         "1000"
 282     }
 283     { $example "USING: math.bitwise kernel prettyprint ;"
 284         "0b1000 3 toggle-bit .b"
 285         "0"
 286     }
 287 } ;
 288
 289 HELP: set-bit
 290 { $values
 291      { "x" integer } { "n" integer }
 292      { "y" integer }
 293 }
 294 { $description "Sets the nth bit of " { $snippet "x" } "." }
 295 { $examples
 296     { $example "USING: math.bitwise kernel prettyprint ;"
 297         "0 5 set-bit .h"
 298         "20"
 299     }
 300 } ;
 301
 302 HELP: shift-mod
 303 { $values
 304      { "m" integer } { "s" integer } { "w" integer }
 305      { "n" integer }
 306 }
 307 { $description "Calls " { $link shift } " on " { $snippet "n" } " and " { $snippet "s" } ", wrapping the result to " { $snippet "w" } " bits." } ;
 308
 309 HELP: unmask
 310 { $values
 311      { "x" integer } { "n" integer }
 312      { "?" "a boolean" }
 313 }
 314 { $description "Clears the bits in " { $snippet "x" } " if they are set in the mask " { $snippet "n" } "." }
 315 { $examples
 316     { $example "USING: math.bitwise kernel prettyprint ;"
 317         "0xff 0x0f unmask .h"
 318         "f0"
 319     }
 320 } ;
 321
 322 HELP: unmask?
 323 { $values
 324      { "x" integer } { "n" integer }
 325      { "?" "a boolean" }
 326 }
 327 { $description "Tests whether unmasking the bits in " { $snippet "x" } " would return an integer greater than zero." }
 328 { $examples
 329     { $example "USING: math.bitwise kernel prettyprint ;"
 330         "0xff 0x0f unmask? ."
 331         "t"
 332     }
 333 } ;
 334
 335 HELP: w*
 336 { $values
 337      { "x" integer } { "y" integer }
 338      { "z" integer }
 339 }
 340 { $description "Multiplies two integers and wraps the result to a 32-bit unsigned integer." }
 341 { $examples
 342     { $example "USING: math.bitwise kernel prettyprint ;"
 343         "0xffffffff 0x2 w* ."
 344         "4294967294"
 345     }
 346 } ;
 347
 348 HELP: w+
 349 { $values
 350      { "x" integer } { "y" integer }
 351      { "z" integer }
 352 }
 353 { $description "Adds two integers and wraps the result to a 32-bit unsigned integer." }
 354 { $examples
 355     { $example "USING: math.bitwise kernel prettyprint ;"
 356         "0xffffffff 0x2 w+ ."
 357         "1"
 358     }
 359 } ;
 360
 361 HELP: w-
 362 { $values
 363      { "x" integer } { "y" integer }
 364      { "z" integer }
 365 }
 366 { $description "Subtracts two integers and wraps the result to a 32-bit unsigned integer." }
 367 { $examples
 368     { $example "USING: math.bitwise kernel prettyprint ;"
 369         "0x0 0xff w- ."
 370         "4294967041"
 371     }
 372 } ;
 373
 374 HELP: W*
 375 { $values
 376      { "x" integer } { "y" integer }
 377      { "z" integer }
 378 }
 379 { $description "Multiplies two integers and wraps the result to a 64-bit unsigned integer." }
 380 { $examples
 381     { $example "USING: math.bitwise kernel prettyprint ;"
 382         "0xffffffffffffffff 0x2 W* ."
 383         "18446744073709551614"
 384     }
 385 } ;
 386
 387 HELP: W+
 388 { $values
 389      { "x" integer } { "y" integer }
 390      { "z" integer }
 391 }
 392 { $description "Adds two integers and wraps the result to 64-bit unsigned integer." }
 393 { $examples
 394     { $example "USING: math.bitwise kernel prettyprint ;"
 395         "0xffffffffffffffff 0x2 W+ ."
 396         "1"
 397     }
 398 } ;
 399
 400 HELP: W-
 401 { $values
 402      { "x" integer } { "y" integer }
 403      { "z" integer }
 404 }
 405 { $description "Subtracts two integers and wraps the result to a 64-bit unsigned integer." }
 406 { $examples
 407     { $example "USING: math.bitwise kernel prettyprint ;"
 408         "0x0 0xff W- ."
 409         "18446744073709551361"
 410     }
 411 } ;
 412
 413 HELP: wrap
 414 { $values
 415      { "m" integer } { "n" integer }
 416      { "m'" integer }
 417 }
 418 { $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." }
 419 { $examples "Equivalent to modding by 8:"
 420     { $example
 421         "USING: math.bitwise prettyprint ;"
 422         "0xffff 8 wrap .h"
 423         "7"
 424     }
 425 } ;
 426
 427 ARTICLE: "math-bitfields" "Constructing bit fields"
 428 "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:"
 429 { $subsections bitfield } ;
 430
 431 ARTICLE: "math.bitwise" "Additional bitwise arithmetic"
 432 "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."
 433 $nl
 434 "Setting and clearing bits:"
 435 { $subsections
 436     set-bit
 437     clear-bit
 438 }
 439 "Testing if bits are set or clear:"
 440 { $subsections
 441     bit?
 442     bit-clear?
 443 }
 444 "Toggling a bit:"
 445 { $subsections
 446     toggle-bit
 447 }
 448 "Operations with bitmasks:"
 449 { $subsections
 450     mask
 451     unmask
 452     mask?
 453     unmask?
 454 }
 455 "Generating an integer with n set bits:"
 456 { $subsections on-bits }
 457 "Counting the number of set bits:"
 458 { $subsections bit-count }
 459 "Testing the parity of an object:"
 460 { $subsections even-parity? odd-parity? }
 461 "More efficient modding by powers of two:"
 462 { $subsections wrap }
 463 "Bit-rolling:"
 464 { $subsections
 465     bitroll
 466     bitroll-32
 467     bitroll-64
 468 }
 469 "32-bit arithmetic:"
 470 { $subsections
 471     w+
 472     w-
 473     w*
 474 }
 475 "64-bit arithmetic:"
 476 { $subsections
 477     W+
 478     W-
 479     W*
 480 }
 481 "Converting a number to the nearest even/odd:"
 482 { $subsections
 483     >even
 484     >odd
 485 }
 486 "Bitfields:"
 487 { $subsections
 488     "math-bitfields"
 489 } ;
 490
 491 ABOUT: "math.bitwise"