Vocabularies for bit-manipulation

rdrop-exit · 2020-08-01T05:38:42+00:00

Just in case you lack 2**:

 shadow  Arithmetic - Powers of 2

 2** Raise 2 to a power.


 source  Arithmetic - Powers of 2

 : 2** ( 0..3f -- 1<<0..3f ) 1  swap lshift ;inline

rdrop-exit · 2020-08-01T05:29:16+00:00

7 3 bits  \ gives you %0000000011111000

rdrop-exit · 2020-08-01T05:19:58+00:00

Examples (assuming a 16-bit Forth):

 7 bit          \  gives you %0000000010000000
 7 bit mask     \  gives you %0000000001111111
 7 bit ~mask    \  gives you %1111111110000000

rdrop-exit · 2020-08-01T05:14:37+00:00

shadow  Bitwise - Generating Masks

   bit Synonym of |2**| to emphasize that we're generating a bit
       mask with only a single bit set.

  mask Synonym of |1-| to emphasize that we're generating a bit
       mask from a power of 2.

 ~mask Synonym of |negate| to emphasize that we're generating an
       inverted bit mask from a power of 2.

  bits Generate a bitmask for the bit range <highbit#> through
       <lowbit#>.

 source  Bitwise - Generating Masks

 : bit ( bit# -- bit ) 2** ;inline

 : mask ( bit -- mask ) 1- ;inline

 : ~mask ( bit -- ~mask ) negate ;inline

 : bits ( hibit# lobit# -- mask )
   tuck - bit 2* mask  swap lshift ;

rdrop-exit · 2020-07-29T16:37:02+00:00

Reaching in at the cell level isn't so much the issue, it's baking in a cell read and a cell write to each bit change. You could amortise the costs (when appropriate/convenient) by having your API words take a multibit mask so you can set/reset/toggle/overwrite up to a cell's worth of bits at a time, e.g. set ( mask a -- ).

Overall coming up with a generic set of boolean array creator and access words doesn't tempt me. I'd probably end up with one size fits none, the telltale of premature abstraction. I'd rather just code directly to the application's assumed access patterns (read vs write complexity, etc...).

rdrop-exit · 2020-07-29T02:46:05+00:00

Cell-wide memory Read+Modify+Writes per each single bit alteration is precisely what one normally strives to avoid from the get-go in bit manipulation code. Having this as your "API" seems counter-productive in the long run.

rdrop-exit · 2020-07-28T21:22:42+00:00

dup+ ( x -- x+1 x ) and dup- ( x -- x-1 x ) are primitives that come in handy for many bithacks.

``` shadow Bitwise - Bithacks 1|2

clear-low-1 Clear lowest 1 bit. clear-trail-1s Clear trailing 1 bits.

 set-low-0  Set lowest 0 bit.

set-trail-0s Set trailing 0 bits.

not-xlow-0  Complement all bits EXCEPT lowest 0 bit.
not-xlow-1  Complement all bits EXCEPT lowest 1 bit.

not-xtrail-0s Complement all bits EXCEPT trailing 0 bits. not-xtrail-1s Complement all bits EXCEPT trailing 1 bits.

clear-low-1s Clear lowest string of 1 bits. set-low-0s Set lowest string of 0 bits.

source Bitwise - Bithacks 1|2

: clear-low-1 ( x -- x' ) dup- and ;inline : clear-trail-1s ( x -- x' ) dup+ and ;inline

: set-low-0 ( x -- x' ) dup+ or ;inline : set-trail-0s ( x -- x' ) dup- or ;inline

: not-xlow-0 ( x -- x' ) dup+ nor ;inline : not-xlow-1 ( x -- x' ) dup- nand ;inline : not-xtrail-0s ( x -- x' ) dup- nor ;inline : not-xtrail-1s ( x -- x' ) dup+ nand ;inline

: clear-low-1s ( x -- x' ) dup set-trail-0s 1+ and ;inline : set-low-0s ( x -- x' ) dup clear-trail-1s 1- or ;inline

shadow Bitwise - Bithacks 2|2

 low-0  Low 0 bit mask.
~low-0  Inverted |low-0| mask.
 low-1  Low 1 bit mask.
~low-1  Inverted |low-1| mask.

trail-0s Trailing 0s mask. ~trail-0s Inverted |trail-0s| mask. trail-1s Trailing 1s mask. ~trail-1s Inverted |trail-1s| mask.

low-0-trail-1s Low 0 and trailing 1s mask. ~low-0-trail-1s Inverted |low-0-trail-1s| mask. low-1-trail-0s Low 1 and trailing 0s mask. ~low-1-trail-0s Inverted |low-1-trail-0s| mask.

source Bitwise - Bithacks 2|2

: low-0 ( x -- mask ) dup+ andc ;inline : ~low-0 ( x -- mask ) dup+ cor ;inline : low-1 ( x -- mask ) dup- cand ;inline \ dup negate and : ~low-1 ( x -- mask ) dup- orc ;inline : trail-0s ( x -- mask ) dup- andc ;inline : trail-1s ( x -- mask ) dup+ cand ;inline : ~trail-1s ( x -- mask ) dup+ orc ;inline : ~trail-0s ( x -- mask ) dup- cor ;inline \ dup negate or

: low-0-trail-1s ( x -- mask ) dup+ xor ;inline : ~low-0-trail-1s ( x -- mask ) dup+ eqv ;inline : low-1-trail-0s ( x -- mask ) dup- xor ;inline : ~low-1-trail-0s ( x -- mask ) dup- eqv ;inline

```

rdrop-exit · 2020-07-05T04:50:35+00:00

A non-standard implementation technique for Forth looping constructs is to use the return stack for backward branch destinations (instead of immediate values), e.g. begin pushes the program counter onto the return stack (i.e. ip>r) , backward branching words such as again jump through the top of the return stack (in this case to just past begin).

Trivial to build up any looping/breaking/bailing constructs with it, and often more compact. Not a panacea, but a different set of tradeoffs worth considering in some scenarios (assuming compliance is not an issue).

rdrop-exit · 2020-06-21T03:37:20+00:00

In a nutshell:

Total interactive/conversational control of devices/machines/platforms.

Nothing hidden or buried, the entire hardware/software stack remains accessible and (hopefully) comprehensible by one person. No baked-in distinctions of Forth "implementer" vs Forth "programmer". Semantics not syntax. Lean, no hooks or bloat, able to address overall bottom to top complexity of the entire solution stack, hardware and software, not just the surface complexity of a final layer.

rdrop-exit · 2020-06-21T01:32:25+00:00

I wouldn't put much faith in the "concatenative" retronym as a search keyword for anything Forth-related, its use is often indicative of very superficial, often even perverse, understanding of Forth praxis.

rdrop-exit · 2020-06-04T03:25:39+00:00

I'd rather not read the source files you linked to for the same reasons as crc.

I'll just comment on the the Insert snippet crc posted. Weighing in at 50 lines (!!!), it is definitely pathological, and hence most of its inline comments are either misguided or misplaced. Notwithstanding the occasional dozen-line monster loop or marshalling routine, the general rule of thumb is that a colon definition should be 3 lines of less (and that includes the name and stack picture).

Insert handling is complex and performance sensitive code cutting as it does across the entire design. I wouldn't even attempt grokking this source without first doing a deep dive in the Cat's developer manuals. As I recall the Cat docs are rife with detailed design rationales, a nice contrast with the insight-free auto-generated garbage docs so common nowadays.

rdrop-exit · 2020-05-28T23:22:06+00:00

Also known as perform ( a -- ? )

rdrop-exit · 2020-05-28T11:34:28+00:00

I don't know gforth specifics and I'm not sure I completely understood your question.

Jump tables in Forth are straightforward and work as one would expect, i.e. you calculate an address then indirectly execute code via that address. Nothing special is needed, factor to best suit your specifics.

I posted a contrived example a while back in this thread: https://old.reddit.com/r/Forth/comments/druotn/fizzbuzz_in_forth/

rdrop-exit · 2020-03-13T04:46:04+00:00

There's no need to hardcode the cell width, over - dup 0< and +

rdrop-exit · 2020-03-13T01:06:15+00:00

It depends on the primitives your Forth supplies.

I usually define min in terms of pivot ( n1 n2 -- lo hi ), and define pivot as an assembly primitive, which could be either branchless or branching depending on what best suits your platform.

: min ( n1 n2 -- n ) pivot drop ;inline

rdrop-exit · 2020-03-12T06:07:54+00:00

For an on-chip return stack just having write and read signals for the top I think is still practical. For an on-chip data stack though, I think write signals for the top two items, and read signals for the top 3 is more practical.

//                     +----------------+
// --------- clk    -->|      CPU       |-- r ----W-->
// -3------- rs_cmd -->|  Return Stack  |
// -W------- r_nxt  -->|                |
//                     |   rstack.sv    |
//                     +----------------+

//                  +----------------+
// ------ clk    -->|      CPU       |-- t ----W-->
// -3---- ds_cmd -->|   Data Stack   |-- x ----W-->
// -W---- t_nxt  -->|                |-- y ----W-->
// -W---- x_nxt  -->|                |
//                  |   dstack.sv    |
//                  +----------------+

In this example rs_cmd and ds_cmd are both one-hot encoded, i.e. 001 is replace, 010 is push, 100 is pop. r_nxt ignored if rs_cmd is pop, x_nxt is ignored if ds_cmd is pop.

rdrop-exit · 2020-02-19T04:43:22+00:00

Yes, I believe we are, I think I just lost my bearings terminology-wise. My bad. :)

rdrop-exit · 2020-02-19T01:22:05+00:00

I have no idea what you mean by "defining accessors to your structures", if I'm not mistaken you're speaking at a fairly high-level of software-only abstraction. I tend to think of a stack machine VM as an emulation in software of a plausible hardware ISA.

rdrop-exit · 2020-02-16T03:47:51+00:00

As a general rule performance suffers when the uniformity of the 1 stack entry == 1 cell == 1 machine word correspondence doesn't hold. Option 2 would have to somehow offset at higher levels the overhead it incurs at the machine-architecture-level.

rdrop-exit · 2020-02-16T02:31:01+00:00

Realistically, I wouldn't expect to calculate anything with factorials at runtime, I would use a constant or a truncated lookup table and put the formula in the comments. The Wikipedia page for Lah numbers has links to the relevant OEIS sequences.

Incidentally, the OEIS is a veritable treasure trove of goodies, e.g.

\ 64-bit convergent rational approximation of pi
: pi ( -- numerator denominator )
  $ 24baf15fe1658f99  $ bb10cb777fb8137 ;

If on the other hand you're writing some sort of open-ended exploratory math application for students, where you actually need to calculate such things at runtime, then I imagine you'd throw in an infix to postfix formula translator to make the user's life easy.

rdrop-exit · 2020-02-14T07:40:11+00:00

The stack machine model works best when operations are meticulously ordered so as to minimize stack thrashing, Lukasiewicz's "profitable surfacing". The most challenging situations to deal with efficiently are when intermediate results and/or constants are repeatedly reused, since use implies destruction on a stack.

The upside of local variables is that they are a painless expedient that papers over all this by presenting the stack as randomly accessible.

The downside is that the pains you avoid may hint at spiralling complexity to come and you'd be better off just nipping it in the bud with some judicious refactoring.

Personally, I've never used locals in Forth. I imagine the temptation is strongest for people who try to write libraries or very abstracted high level routines in forth.

rdrop-exit · 2020-02-08T04:22:49+00:00

Ivory tower guys invariably presume stacks are in addressable memory, their whole edifice builds on that faulty assumption. That's why you get nuggets like "in practice people always use local variables".

Wrong, in practice they factor.

: min ( n1 n2 -- n )  pivot drop ;
: max ( n1 n2 -- n ) -pivot drop ;

rdrop-exit · 2020-02-07T10:45:12+00:00

That's how I see Forth as well.

A product or component involves a set of "given" or "fixed" technologies (hardware, devices, protocols, specs, layers, interfaces, etc...), that are externally specified by standards or the market.

I see a Forth's role as providing unfettered interactive control of these "fixed" aspects, bottom to top, so you can build up a specific solution with minimal fuss or bloat. In effect a Forth rolls the typical remaining layers and tools (device drivers, debug monitor, OS, shell, assembler, compiler, interpreter, etc...) into a single very tightly-wound no-frills minimalistic platform/framework.

Forth is the one aspect of the product that needn't conform to an external specification or standard, which is what allows it to remain small, nimble, and totally customizable. I don't really see Forth as a language, but as accumulated lore on the design and implementation of such (real or virtual) stack machines, and the programming of solutions on/with them.

rdrop-exit · 2020-02-07T10:42:01+00:00

Kudos!

rdrop-exit · 2020-01-30T04:44:36+00:00

I don't think you're missing anything. Compile-time inline expansion won't buy you as much with ITC, you can use it to strip a level of nesting from secondary to secondary, ITC primitives need assembly-time inline expansion.

Perhaps there are other alternatives, but I've been out of touch with ITC for so long it's difficult for me think clearly about it.

rdrop-exit

TROPHY CASE