Standard source definitions of DLSHIFT and DRSHIFT (double number left
shift and right shift), over full shift range, per discussion in prior
thread.

Tests needed.

--
Krishna Myneni

=== Start Code ===

1 cells 3 lshift constant BITS_PER_CELL
BITS_PER_CELL 2* constant BITS_PER_DOUBLE

\ Return the u least significant bits of cell value u1
\ as the most significant bits of u2
: lsbits ( u1 u -- u2 )
BITS_PER_CELL min
BITS_PER_CELL - negate
lshift ;

\ Return the u most significant bits of cell value u1
\ as the least significant bits of u2
: msbits ( u1 u -- u2 )
BITS_PER_CELL min
BITS_PER_CELL - negate
rshift ;

0 value ubits

\ u is the number of bits to shift

: DLSHIFT ( ud u -- ud2 )
dup 0= IF drop EXIT THEN
BITS_PER_DOUBLE min dup to ubits
BITS_PER_CELL > IF
drop \ high double has been left shifted out
ubits BITS_PER_CELL - lshift
0 swap \ new low double
ELSE
ubits lshift swap
dup >r
ubits msbits or
r> ubits lshift
swap
THEN ;

: DRSHIFT ( ud u -- ud2 )
dup 0= IF drop EXIT THEN
BITS_PER_DOUBLE min dup to ubits
BITS_PER_CELL > IF
nip \ low double has been right shifted out
ubits BITS_PER_CELL - rshift
0 \ new high double
ELSE
swap ubits rshift
swap dup >r
ubits lsbits or
r> ubits rshift
THEN ;

=== End Code ===

On 3/26/24 17:01, Krishna Myneni wrote:
> Standard source definitions of DLSHIFT and DRSHIFT (double number left
> shift and right shift), over full shift range, per discussion in prior
> thread.
>
> Tests needed.

Just tested DLSHIFT and found weird things going on. Traced the problem
to LSHIFT.

kforth64

1 64 LSHIFT . \ expected to get zero
1 \ instead, got 1

Then, I looked at the spec. for LSHIFT and, indeed, there is an
ambiguous condition for u >= BITS_PER_CELL .

6.1.1805
LSHIFT “l-shift”
CORE
( x1 u – – x2 )
Perform a logical left shift of u bit-places on x1, giving x2. Put
zeroes into the least significant bits vacated by the shift. An
ambiguous condition exists if u is greater than or equal to the number
of bits in a cell.

Gforth does the same thing

1 64 LSHIFT . 1
1 65 LSHIFT . 2
etc.

We shouldn't have an ambiguous condition here because of some
idiosyncratic behavior of the SHL instruction!

u 64 LSHIFT should be zero on all systems with cell sizes up to 64 bits.

--
Krishna

On 3/26/24 17:01, Krishna Myneni wrote:
> Standard source definitions of DLSHIFT and DRSHIFT (double number left
> shift and right shift), over full shift range, per discussion in prior
> thread.
> ...

This version fixes the issue with the ambiguity of LSHIFT and RSHIFT,
and gives the behavior of DLSHIFT and DRSHIFT which I want. Tests
included below for 32-bit and 64-bit systems.

--
KM

=== dshift.4th ===
\ dshift.4th
\ \ Source code definitions of DLSHIFT and DRSHIFT

1 cells 3 lshift constant BITS_PER_CELL
BITS_PER_CELL 2* constant BITS_PER_DOUBLE

\ Return the u least significant bits of cell value u1
\ as the most significant bits of u2
: lsbits ( u1 u -- u2 )
BITS_PER_CELL min
BITS_PER_CELL - negate
lshift ;

\ Return the u most significant bits of cell value u1
\ as the least significant bits of u2
: msbits ( u1 u -- u2 )
BITS_PER_CELL min
BITS_PER_CELL - negate
rshift ;

0 value ubits

\ u is the number of bits to shift

: DLSHIFT ( ud u -- ud2 )
dup 0= IF drop EXIT THEN
BITS_PER_DOUBLE min dup to ubits
BITS_PER_CELL >= IF
drop \ high double has been left shifted out
ubits BITS_PER_CELL -
dup BITS_PER_CELL = IF
2drop 0 0
ELSE
lshift 0 swap
THEN
ELSE
ubits lshift swap
dup >r
ubits msbits or
r> ubits lshift
swap
THEN ;

: DRSHIFT ( ud u -- ud2 )
dup 0= IF drop EXIT THEN
BITS_PER_DOUBLE min dup to ubits
BITS_PER_CELL >= IF
nip \ low double has been right shifted out
ubits BITS_PER_CELL -
dup BITS_PER_CELL = IF
2drop 0 0
ELSE
rshift 0
THEN
ELSE
swap ubits rshift
swap dup >r
ubits lsbits or
r> ubits rshift
THEN ;

=== End of dshift.4th ===

Test Code

=== dshift-test.4th ===
\ dshift-test.4th
\ include ans-words \ <-- only for kForth
include ttester
include dshift

HEX

TESTING DLSHIFT DRSHIFT

t{ 03 01 BITS_PER_CELL dlshift -> 00 03 }t
t{ FF 00 BITS_PER_CELL dlshift -> 00 FF }t
t{ 00 01 BITS_PER_CELL drshift -> 01 00 }t
t{ 00 FF BITS_PER_CELL drshift -> FF 00 }t
t{ -1 -1 BITS_PER_DOUBLE dlshift -> 00 00 }t
t{ -1 -1 BITS_PER_DOUBLE drshift -> 00 00 }t

BITS_PER_CELL 20 = [IF]
t{ 03 01 BITS_PER_CELL 1- dlshift -> 80000000 80000001 }t
t{ 80000000 02 1 dlshift -> 00 05 }t
t{ 07 03 1 drshift -> 80000003 01 }t
[THEN]

BITS_PER_CELL 40 = [IF]
t{ 03 01 BITS_PER_CELL 1- dlshift -> 8000000000000000 8000000000000001 }t
t{ 8000000000000000 02 1 dlshift -> 00 05 }t
t{ 07 03 1 drshift -> 8000000000000003 01 }t
[THEN]

DECIMAL

=== end of dshift-test.4th ===

Krishna Myneni <krishna.myneni@ccreweb.org> writes:
>1 64 LSHIFT . \ expected to get zero
>1 \ instead, got 1
>
>Then, I looked at the spec. for LSHIFT and, indeed, there is an
>ambiguous condition for u >= BITS_PER_CELL .
>
>
>6.1.1805
>LSHIFT “l-shift”
>CORE
>( x1 u – – x2 )
>Perform a logical left shift of u bit-places on x1, giving x2. Put
>zeroes into the least significant bits vacated by the shift. An
>ambiguous condition exists if u is greater than or equal to the number
>of bits in a cell.
>
>Gforth does the same thing
>
>1 64 LSHIFT . 1
>1 65 LSHIFT . 2
>etc.
>
>
>We shouldn't have an ambiguous condition here because of some
>idiosyncratic behavior of the SHL instruction!

On one hand, programmers expect the result of ( n m ) LSHIFT and ( n m
) RSHIFT to be 0 when m>=CELL_BITS. As you write:

>u 64 LSHIFT should be zero on all systems with cell sizes up to 64 bits.

OTOH, it's relatively rare to need this, so most computer architects
have decided not to pay the relatively small hardware cost to produce
this result, and instead only consider the lower 5 or 6 bits of the
shift amount. The cost in language implementations is a little higher
than at the hardware level, and various programming languages,
including Forth have decided to leave this unspecified (there are also
architectures where one bit more is used, and IIRC also hardware (IIRC
Power) where a result of 0 is guaranteed).

One interesting case is Java, which specifies the language pretty
completely in order to make Java write-once-run-everywhere. Java's
designers chose to go along with the common practice in computer
architecture
<https://docs.oracle.com/javase/specs/jls/se21/html/jls-15.html#jls-15.19>:

|If the promoted type of the left-hand operand is int, then only the
|five lowest-order bits of the right-hand operand are used as the shift
|distance.

|If the promoted type of the left-hand operand is long, then only the
|six lowest-order bits of the right-hand operand are used as the shift
|distance.

See also
<https://forth-standard.org/standard/core/LSHIFT#contribution-335>.

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: https://forth-standard.org/
EuroForth 2023: https://euro.theforth.net/2023

In article <utvgki$2ciso$1@dont-email.me>,
Krishna Myneni <krishna.myneni@ccreweb.org> wrote:
>Standard source definitions of DLSHIFT and DRSHIFT (double number left
>shift and right shift), over full shift range, per discussion in prior
>thread.
>
>Tests needed.
>
>--
>Krishna Myneni
>
>
>=== Start Code ===
>
>1 cells 3 lshift constant BITS_PER_CELL
>BITS_PER_CELL 2* constant BITS_PER_DOUBLE
>
>\ Return the u least significant bits of cell value u1
>\ as the most significant bits of u2
>: lsbits ( u1 u -- u2 )
> BITS_PER_CELL min
> BITS_PER_CELL - negate
> lshift ;
>
>\ Return the u most significant bits of cell value u1
>\ as the least significant bits of u2
>: msbits ( u1 u -- u2 )
> BITS_PER_CELL min
> BITS_PER_CELL - negate
> rshift ;
>
>0 value ubits
>
>\ u is the number of bits to shift
>
>: DLSHIFT ( ud u -- ud2 )
> dup 0= IF drop EXIT THEN
> BITS_PER_DOUBLE min dup to ubits
> BITS_PER_CELL > IF
> drop \ high double has been left shifted out
> ubits BITS_PER_CELL - lshift
> 0 swap \ new low double
> ELSE
> ubits lshift swap
> dup >r
> ubits msbits or
> r> ubits lshift
> swap
> THEN ;
>
>: DRSHIFT ( ud u -- ud2 )
> dup 0= IF drop EXIT THEN
> BITS_PER_DOUBLE min dup to ubits
> BITS_PER_CELL > IF
> nip \ low double has been right shifted out
> ubits BITS_PER_CELL - rshift
> 0 \ new high double
> ELSE
> swap ubits rshift
> swap dup >r
> ubits lsbits or
> r> ubits rshift
> THEN ;
>
>=== End Code ===

These words should be in assembler anyway.
So a rigorous testset is more valuable than a supposedly
standard implementation.

Groetjes Albert
--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat purring. - the Wise from Antrim -

On 2024-03-27 04:57, Krishna Myneni wrote:
> On 3/26/24 17:01, Krishna Myneni wrote:
>> Standard source definitions of DLSHIFT and DRSHIFT (double number left
>> shift and right shift), over full shift range, per discussion in prior
>> thread.
>>
>> Tests needed.
>
> Just tested DLSHIFT and found weird things going on. Traced the problem
> to LSHIFT.
>
>
> kforth64
>
> 1 64 LSHIFT .  \ expected to get zero
> 1              \ instead, got 1
>
> Then, I looked at the spec. for LSHIFT and, indeed, there is an
> ambiguous condition for u >= BITS_PER_CELL .
>
>
> 6.1.1805
> LSHIFT “l-shift”
> CORE
> ( x1 u – – x2 )
> Perform a logical left shift of u bit-places on x1, giving x2. Put
> zeroes into the least significant bits vacated by the shift. An
> ambiguous condition exists if u is greater than or equal to the number
> of bits in a cell.
>
[...]
> We shouldn't have an ambiguous condition here because of some
> idiosyncratic behavior of the SHL instruction!
>
> u 64 LSHIFT should be zero on all systems with cell sizes up to 64 bits.

Ideally — yes.

My rationale (see [1]) is that for any `x` and `u`, the result of a
single shift of `x` by `u` bits should always be equivalent to `u`
sequential shifts by 1 bit.

But neither the standard nor implementations follow this idea.

And I agree, this is rarely needed. So if a program requires this
behavior, it can test the behavior of "shift" operations in this regard
and redefine them in its own word list as:

: lshift ( x u -- x )
dup bits_per_cell u< if lshift exit then
2drop 0
;

[1] An ambiguous condition in LSHIFT (2024-02-05)
<https://forth-standard.org/standard/core/LSHIFT#contribution-335>

--
Ruvim

On 3/27/24 06:26, Ruvim wrote:
> On 2024-03-27 04:57, Krishna Myneni wrote:
>> On 3/26/24 17:01, Krishna Myneni wrote:
>>> Standard source definitions of DLSHIFT and DRSHIFT (double number
>>> left shift and right shift), over full shift range, per discussion in
>>> prior thread.
>>>
>>> Tests needed.
>>
>> Just tested DLSHIFT and found weird things going on. Traced the
>> problem to LSHIFT.
>>
>>
>> kforth64
>>
>> 1 64 LSHIFT .  \ expected to get zero
>> 1              \ instead, got 1
>>
>> Then, I looked at the spec. for LSHIFT and, indeed, there is an
>> ambiguous condition for u >= BITS_PER_CELL .
>>
>>
>> 6.1.1805
>> LSHIFT “l-shift”
>> CORE
>> ( x1 u – – x2 )
>> Perform a logical left shift of u bit-places on x1, giving x2. Put
>> zeroes into the least significant bits vacated by the shift. An
>> ambiguous condition exists if u is greater than or equal to the number
>> of bits in a cell.
>>
> [...]
>> We shouldn't have an ambiguous condition here because of some
>> idiosyncratic behavior of the SHL instruction!
>>
>> u 64 LSHIFT should be zero on all systems with cell sizes up to 64 bits.
>
> Ideally — yes.
>
> My rationale (see [1]) is that for any `x` and `u`, the result of a
> single shift of `x` by `u` bits should always be equivalent to `u`
> sequential shifts by 1 bit.
>

I really think it is a bad idea to have UB in the spec of LSHIFT and
RSHIFT due to the arbitrariness of low level shift operations at the
hardware level. Here we have a chance to remove that UB and guarantee that

1 BITS_PER_CELL LSHIFT returns zero
and
1 BITS_PER_CELL RSHIFT returns zero

so that the expected result for a shift operation on the cell operand
does not have UB.

Efficiency because of extra instructions needed to implement this
guarantee are not even worth bothering about -- we are not C.

One would also expect the following two expressions to be consistent

1 64 LSHIFT .

and

: TEST2* 1 64 0 DO 2* LOOP . ;
TEST2*

Currently, on some systems (kForth and Gforth), we get,

1 64 LSHIFT . \ gives 1
TEST2* \ gives 0

For system implementers to ensure LSHIFT uses 6 bits of the shift count
would be trivial and should not break past code provided that code did
not use specific behavior which was called out as undefined behavior in
the standard.

If we get enough common practice in systems to have LSHIFT and RSHIFT
behave in a consistent and expected manner, then it can be standardized.
The important thing is to avoid nonsense in the language spec because of
low-level hardware choices.

--
Krishna

On 3/27/24 02:53, Anton Ertl wrote:
> Krishna Myneni <krishna.myneni@ccreweb.org> writes:
>> 1 64 LSHIFT . \ expected to get zero
>> 1 \ instead, got 1
>>
>> Then, I looked at the spec. for LSHIFT and, indeed, there is an
>> ambiguous condition for u >= BITS_PER_CELL .
>>
>>
>> 6.1.1805
>> LSHIFT “l-shift”
>> CORE
>> ( x1 u – – x2 )
>> Perform a logical left shift of u bit-places on x1, giving x2. Put
>> zeroes into the least significant bits vacated by the shift. An
>> ambiguous condition exists if u is greater than or equal to the number
>> of bits in a cell.
>>
....
>
> One interesting case is Java, which specifies the language pretty
> completely in order to make Java write-once-run-everywhere. Java's
> designers chose to go along with the common practice in computer
> architecture
> <https://docs.oracle.com/javase/specs/jls/se21/html/jls-15.html#jls-15.19>:
>
> |If the promoted type of the left-hand operand is int, then only the
> |five lowest-order bits of the right-hand operand are used as the shift
> |distance.
>
> |If the promoted type of the left-hand operand is long, then only the
> |six lowest-order bits of the right-hand operand are used as the shift
> |distance.
>

For Forth, it would seem reasonable and natural to guarantee that the
number of bits in the shift count which are honored are enough to
represent the data stack width in bits. This would ensure that

1 u LSHIFT

and

-1 u RSHIFT

would be zero for u >= BITS_PER_CELL.

--
Krishna

On 3/27/24 03:34, albert@spenarnc.xs4all.nl wrote:
> In article <utvgki$2ciso$1@dont-email.me>,
> Krishna Myneni <krishna.myneni@ccreweb.org> wrote:
>> Standard source definitions of DLSHIFT and DRSHIFT (double number left
>> shift and right shift), over full shift range, per discussion in prior
>> thread.
>>
>> Tests needed.
>>
....
>
> These words should be in assembler anyway.
> So a rigorous testset is more valuable than a supposedly
> standard implementation.

There is no standard implementation -- DLSHIFT and DRSHIFT are not
standard words. What I meant by "standard source definitions" is that
the Forth level definitions only use Forth standard words.

Tests for my latest revision are provided.

--
KM

On 27/03/2024 10:26 pm, Ruvim wrote:
> On 2024-03-27 04:57, Krishna Myneni wrote:
> [...]
>> We shouldn't have an ambiguous condition here because of some idiosyncratic behavior of the SHL instruction!
>>
>> u 64 LSHIFT should be zero on all systems with cell sizes up to 64 bits.
>
> Ideally — yes.
>
> My rationale (see [1]) is that for any `x` and `u`, the result of a single shift of `x` by `u` bits should always be equivalent to `u` sequential shifts by 1 bit.
>
> But neither the standard nor implementations follow this idea.

The same occurred with 2/ and 2 / . Those who saw Forth as a language wanted
consistent results; whereas those who saw Forth as a toolkit said give us what
the hardware provides.

On 2024-03-27 07:14, Krishna Myneni wrote:
> On 3/26/24 17:01, Krishna Myneni wrote:
>> Standard source definitions of DLSHIFT and DRSHIFT (double number left
>> shift and right shift), over full shift range, per discussion in prior
>> thread.
>> ...
>
> This version fixes the issue with the ambiguity of LSHIFT and RSHIFT,
> and gives the behavior of DLSHIFT and DRSHIFT which I want. Tests
> included below for 32-bit and 64-bit systems.
>
> --
> KM
>
> === dshift.4th ===
> \ dshift.4th
> \
> \ Source code definitions of DLSHIFT and DRSHIFT
>
> 1 cells 3 lshift constant BITS_PER_CELL
> BITS_PER_CELL 2* constant BITS_PER_DOUBLE
>
> \ Return the u least significant bits of cell value u1
> \ as the most significant bits of u2
> : lsbits ( u1 u -- u2 )
>      BITS_PER_CELL min
>      BITS_PER_CELL - negate
>      lshift ;
>
> \ Return the u most significant bits of cell value u1
> \ as the least significant bits of u2
> : msbits ( u1 u -- u2 )
>      BITS_PER_CELL min
>      BITS_PER_CELL - negate
>      rshift ;
>
> 0 value ubits
>
> \ u is the number of bits to shift
>
> : DLSHIFT ( ud u -- ud2 )
>     dup 0= IF drop EXIT THEN
>     BITS_PER_DOUBLE min dup to ubits
>     BITS_PER_CELL >= IF
>       drop      \ high double has been left shifted out
>       ubits BITS_PER_CELL -
>       dup BITS_PER_CELL = IF
>         2drop 0 0
>       ELSE
>         lshift 0 swap
>       THEN
>     ELSE
>       ubits lshift swap
>       dup >r
>       ubits msbits or
>       r> ubits lshift
>       swap
>     THEN ;
>
> : DRSHIFT ( ud u -- ud2 )
>     dup 0= IF drop EXIT THEN
>     BITS_PER_DOUBLE min dup to ubits
>     BITS_PER_CELL >= IF
>       nip    \ low double has been right shifted out
>       ubits BITS_PER_CELL -
>       dup BITS_PER_CELL = IF
>         2drop 0 0
>       ELSE
>         rshift 0
>       THEN
>     ELSE
>       swap ubits rshift
>       swap dup >r
>       ubits lsbits or
>       r> ubits rshift
>     THEN ;
>
> === End of dshift.4th ===

I wrote a simpler implementation a long time ago. The file
"double-shift.fth" below is a translation from [2] using different names
for constants.

=== "double-shift.fth"

:NONAME 0 -1 BEGIN DUP WHILE SWAP 1+ SWAP 1 RSHIFT REPEAT DROP ; EXECUTE
CONSTANT BITS-PER-CELL

BITS-PER-CELL 1- CONSTANT MAX-FOR-SHIFT1
BITS-PER-CELL 2* 1- CONSTANT MAX-FOR-SHIFT2

: (DLSHIFT) ( xd1 u -- xd2 )
( x.lo x.hi u )
TUCK LSHIFT >R
2DUP NEGATE BITS-PER-CELL + RSHIFT >R
LSHIFT 2R> OR
; : DLSHIFT ( xd1 u -- xd2 )
DUP 0= IF DROP EXIT THEN
DUP MAX-FOR-SHIFT2 U> IF DROP 2DROP 0. EXIT THEN
DUP MAX-FOR-SHIFT1 U> IF NIP BITS-PER-CELL - LSHIFT 0 SWAP EXIT THEN
(DLSHIFT)
; : (DRSHIFT) ( xd1 u -- xd2 )
( x.lo x.hi u )
2DUP RSHIFT >R
TUCK NEGATE BITS-PER-CELL + LSHIFT >R
RSHIFT R> OR R>
; : DRSHIFT ( xd1 u -- xd2 )
DUP 0= IF DROP EXIT THEN
DUP MAX-FOR-SHIFT2 U> IF DROP 2DROP 0. EXIT THEN
DUP MAX-FOR-SHIFT1 U> IF >R NIP R> BITS-PER-CELL - RSHIFT 0 EXIT THEN
(DRSHIFT)
;

=== End of "double-shift.fth"

[2] Low-level definition for doubling cell size (in ForthML)
<https://github.com/rufig/spf4-utf8/blob/master/devel/~pinka/model/forthproc/doubling-cell.f.xml>

--
Ruvim

On 3/27/24 09:56, Ruvim wrote:
> On 2024-03-27 07:14, Krishna Myneni wrote:
>> On 3/26/24 17:01, Krishna Myneni wrote:
>>> Standard source definitions of DLSHIFT and DRSHIFT (double number
>>> left shift and right shift), over full shift range, per discussion in
>>> prior thread.
>>> ...
....
>
> I wrote a simpler implementation a long time ago. The file
> "double-shift.fth" below is a translation from [2] using different names
> for constants.
>
>
> === "double-shift.fth"
>
> :NONAME 0 -1 BEGIN DUP WHILE SWAP 1+ SWAP 1 RSHIFT REPEAT DROP ; EXECUTE
> CONSTANT BITS-PER-CELL
>
> BITS-PER-CELL 1-      CONSTANT MAX-FOR-SHIFT1
> BITS-PER-CELL 2* 1-   CONSTANT MAX-FOR-SHIFT2
>
> : (DLSHIFT) ( xd1 u -- xd2 )
>   ( x.lo x.hi  u )
>   TUCK LSHIFT >R
>   2DUP NEGATE BITS-PER-CELL + RSHIFT >R
>   LSHIFT 2R> OR
> ;
> : DLSHIFT ( xd1 u -- xd2 )
>   DUP 0= IF  DROP EXIT THEN
>   DUP MAX-FOR-SHIFT2 U> IF  DROP 2DROP 0. EXIT THEN
>   DUP MAX-FOR-SHIFT1 U> IF  NIP BITS-PER-CELL - LSHIFT 0 SWAP EXIT THEN
>   (DLSHIFT)
> ;
> : (DRSHIFT) ( xd1 u -- xd2 )
>   ( x.lo x.hi  u )
>   2DUP RSHIFT >R
>   TUCK NEGATE BITS-PER-CELL + LSHIFT >R
>   RSHIFT R> OR R>
> ;
> : DRSHIFT ( xd1 u -- xd2 )
>   DUP 0= IF  DROP EXIT THEN
>   DUP MAX-FOR-SHIFT2 U> IF  DROP 2DROP 0. EXIT THEN
>   DUP MAX-FOR-SHIFT1 U> IF  >R NIP R> BITS-PER-CELL - RSHIFT 0 EXIT THEN
>   (DRSHIFT)
> ;
>
> === End of "double-shift.fth"
>

Does it succeed on all of the tests I gave?

--
Krishna

On 3/27/24 08:57, dxf wrote:
> On 27/03/2024 10:26 pm, Ruvim wrote:
>> On 2024-03-27 04:57, Krishna Myneni wrote:
>> [...]
>>> We shouldn't have an ambiguous condition here because of some idiosyncratic behavior of the SHL instruction!
>>>
>>> u 64 LSHIFT should be zero on all systems with cell sizes up to 64 bits.
>>
>> Ideally — yes.
>>
>> My rationale (see [1]) is that for any `x` and `u`, the result of a single shift of `x` by `u` bits should always be equivalent to `u` sequential shifts by 1 bit.
>>
>> But neither the standard nor implementations follow this idea.
>
> The same occurred with 2/ and 2 / . Those who saw Forth as a language wanted
> consistent results; whereas those who saw Forth as a toolkit said give us what
> the hardware provides.
>

If one needs the machine shift instructions, they should be using the
Forth assembler to write the word in which it is needed. The language
specification has no justification (that I can see) for undefined
behavior for the LSHIFT and RSHIFT instructions.

--
Krishna

On 2024-03-27 19:33, Krishna Myneni wrote:
> On 3/27/24 09:56, Ruvim wrote:
>> On 2024-03-27 07:14, Krishna Myneni wrote:
>>> On 3/26/24 17:01, Krishna Myneni wrote:
>>>> Standard source definitions of DLSHIFT and DRSHIFT (double number
>>>> left shift and right shift), over full shift range, per discussion
>>>> in prior thread.
>>>> ...
> ...
>>
>> I wrote a simpler implementation a long time ago. The file
>> "double-shift.fth" below is a translation from [2] using different
>> names for constants.
>>
>>
>> === "double-shift.fth"
>>
>> :NONAME 0 -1 BEGIN DUP WHILE SWAP 1+ SWAP 1 RSHIFT REPEAT DROP ; EXECUTE
>> CONSTANT BITS-PER-CELL
>>
>> BITS-PER-CELL 1-      CONSTANT MAX-FOR-SHIFT1
>> BITS-PER-CELL 2* 1-   CONSTANT MAX-FOR-SHIFT2
>>
>> : (DLSHIFT) ( xd1 u -- xd2 )
>>    ( x.lo x.hi  u )
>>    TUCK LSHIFT >R
>>    2DUP NEGATE BITS-PER-CELL + RSHIFT >R
>>    LSHIFT 2R> OR
>> ;
>> : DLSHIFT ( xd1 u -- xd2 )
>>    DUP 0= IF  DROP EXIT THEN
>>    DUP MAX-FOR-SHIFT2 U> IF  DROP 2DROP 0. EXIT THEN
>>    DUP MAX-FOR-SHIFT1 U> IF  NIP BITS-PER-CELL - LSHIFT 0 SWAP EXIT THEN
>>    (DLSHIFT)
>> ;
>> : (DRSHIFT) ( xd1 u -- xd2 )
>>    ( x.lo x.hi  u )
>>    2DUP RSHIFT >R
>>    TUCK NEGATE BITS-PER-CELL + LSHIFT >R
>>    RSHIFT R> OR R>
>> ;
>> : DRSHIFT ( xd1 u -- xd2 )
>>    DUP 0= IF  DROP EXIT THEN
>>    DUP MAX-FOR-SHIFT2 U> IF  DROP 2DROP 0. EXIT THEN
>>    DUP MAX-FOR-SHIFT1 U> IF  >R NIP R> BITS-PER-CELL - RSHIFT 0 EXIT THEN
>>    (DRSHIFT)
>> ;
>>
>> === End of "double-shift.fth"
>>
>
> Does it succeed on all of the tests I gave?

Of course, I checked — it succeed your tests.

--
Ruvim

On 27.03.2024 13:28, Krishna Myneni wrote:
>
> I really think it is a bad idea to have UB in the spec of LSHIFT and
> RSHIFT due to the arbitrariness of low level shift operations at the
> hardware level.
It's not UB, it is IB and thus it should be required that an implementer
documents the respective behaviour of their system.
> Here we have a chance to remove that UB and guarantee that>
> 1 BITS_PER_CELL LSHIFT  returns zero
> and
> 1 BITS_PER_CELL RSHIFT  returns zero
>
> so that the expected result for a shift operation on the cell operand
> does not have UB.
>
> Efficiency because of extra instructions needed to implement this
> guarantee are not even worth bothering about -- we are not C.
Forth does care about efficiency. Otherwise you could eliminate over the
half of the ambiguous conditions in the Forth standard that only arise
from the fact that hardware platforms differ in their behaviour.
[snip]
For the rare situation that a variable shift count is needed, and is not
per se restricted to 0..ADDRESS-UNIT-BITS - 1, you can always write either
0 MAX S" ADDRESS-UNIT-BITS" 1- MIN LSHIFT ( or RSHIFT)
or
DUP 0< INVERT IF DUP S" ADDRESS-UNIT-BITS" < IF LSHIFT ( or RSHIFT)
ELSE ( whatever to do if shift-amount < 0)
ELSE ( whatever to do if shift-amount >= cell width)
THEN THEN
or simply
DUP 0< ABORT" shift amount less than 0"
DUP S" ADDRESS-UNIT-BITS" 1- > ABORT" shift amount greater/equal cell width)
LSHIFT ( or RSHIFT)

NB: The behaviour of most processors to only regard the 5 or 6 LSBs is
useful for expressions like -1 64 <n> - LSHIFT to produce bit masks,
these can simply be expressed as <n> NEGATE LSHIFT (with an
environmental dependency on processors that behave this way).

--
Bernd Linsel

On 27.03.2024 09:34, albert@spenarnc.xs4all.nl wrote:
> These words should be in assembler anyway.

+1

--
Bernd Linsel

Krishna Myneni <krishna.myneni@ccreweb.org> writes:
>I really think it is a bad idea to have UB in the spec of LSHIFT and
>RSHIFT due to the arbitrariness of low level shift operations at the
>hardware level. Here we have a chance to remove that UB and guarantee that
>
>1 BITS_PER_CELL LSHIFT returns zero
>and
>1 BITS_PER_CELL RSHIFT returns zero
>
>so that the expected result for a shift operation on the cell operand
>does not have UB.

I guess you mean the ambiguous condition in the specification of
LSHIFT and RSHIFT, which is more like implementation-defined behaviour
in some other languages (and the advocates of undefined behaviour make
a lot of wind about the difference between implementation-defined and
undefined).

Well, if you want to see this happen, you have to convince some Forth
system implementors, so common practice moves in the direction you
prefer, and once that is done, make a proposal.

You could point out that the extra cost of the check is only incurred
for shifts with non-constant shift amounts, and if you could provide
data on the frequency of constant and non-constant shift amounts, this
might help convince system implementors. Of course, for commercial
implementors, you may get the usual answer that their customers have
not complained to them, but if you don't try, you can't win.

>Efficiency because of extra instructions needed to implement this
>guarantee are not even worth bothering about -- we are not C.

I am sure someone can produce some saying by Chuck Moore that
contradicts this attitude. Sure, Forth is not C, but it's just as
performance-conscious.

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: https://forth-standard.org/
EuroForth 2023: https://euro.theforth.net/2023

On 3/27/24 11:36, Ruvim wrote:

>>> === "double-shift.fth"
>>>
>>> :NONAME 0 -1 BEGIN DUP WHILE SWAP 1+ SWAP 1 RSHIFT REPEAT DROP ; EXECUTE
>>> CONSTANT BITS-PER-CELL
>>>
>>> BITS-PER-CELL 1-      CONSTANT MAX-FOR-SHIFT1
>>> BITS-PER-CELL 2* 1-   CONSTANT MAX-FOR-SHIFT2
>>>
>>> : (DLSHIFT) ( xd1 u -- xd2 )
>>>    ( x.lo x.hi  u )
>>>    TUCK LSHIFT >R
>>>    2DUP NEGATE BITS-PER-CELL + RSHIFT >R
>>>    LSHIFT 2R> OR
>>> ;
>>> : DLSHIFT ( xd1 u -- xd2 )
>>>    DUP 0= IF  DROP EXIT THEN
>>>    DUP MAX-FOR-SHIFT2 U> IF  DROP 2DROP 0. EXIT THEN
>>>    DUP MAX-FOR-SHIFT1 U> IF  NIP BITS-PER-CELL - LSHIFT 0 SWAP EXIT THEN
>>>    (DLSHIFT)
>>> ;
>>> : (DRSHIFT) ( xd1 u -- xd2 )
>>>    ( x.lo x.hi  u )
>>>    2DUP RSHIFT >R
>>>    TUCK NEGATE BITS-PER-CELL + LSHIFT >R
>>>    RSHIFT R> OR R>
>>> ;
>>> : DRSHIFT ( xd1 u -- xd2 )
>>>    DUP 0= IF  DROP EXIT THEN
>>>    DUP MAX-FOR-SHIFT2 U> IF  DROP 2DROP 0. EXIT THEN
>>>    DUP MAX-FOR-SHIFT1 U> IF  >R NIP R> BITS-PER-CELL - RSHIFT 0 EXIT
>>> THEN
>>>    (DRSHIFT)
>>> ;
>>>
>>> === End of "double-shift.fth"
>>>
>>
>> Does it succeed on all of the tests I gave?
>
> Of course, I checked — it succeed your tests.
>
>

Thanks.

-- KM

On 3/27/24 13:46, Anton Ertl wrote:
> Krishna Myneni <krishna.myneni@ccreweb.org> writes:
>> I really think it is a bad idea to have UB in the spec of LSHIFT and
>> RSHIFT due to the arbitrariness of low level shift operations at the
>> hardware level. Here we have a chance to remove that UB and guarantee that
>>
>> 1 BITS_PER_CELL LSHIFT returns zero
>> and
>> 1 BITS_PER_CELL RSHIFT returns zero
>>
>> so that the expected result for a shift operation on the cell operand
>> does not have UB.
>
> I guess you mean the ambiguous condition in the specification of
> LSHIFT and RSHIFT, which is more like implementation-defined behaviour
> in some other languages (and the advocates of undefined behaviour make
> a lot of wind about the difference between implementation-defined and
> undefined).

I have to admit that the distinction between mapping "ambiguous
condition" to IB vs UB escapes me.

>
> Well, if you want to see this happen, you have to convince some Forth
> system implementors, so common practice moves in the direction you
> prefer, and once that is done, make a proposal.
>

Sure. I would start with modifying LSHIFT and RSHIFT in my own Forth
systems. The revisions would still be consistent with the standard.

> You could point out that the extra cost of the check is only incurred
> for shifts with non-constant shift amounts, and if you could provide
> data on the frequency of constant and non-constant shift amounts, this
> might help convince system implementors. Of course, for commercial
> implementors, you may get the usual answer that their customers have
> not complained to them, but if you don't try, you can't win.
>
>> Efficiency because of extra instructions needed to implement this
>> guarantee are not even worth bothering about -- we are not C.
>
> I am sure someone can produce some saying by Chuck Moore that
> contradicts this attitude. Sure, Forth is not C, but it's just as
> performance-conscious.
>

My meaning was that I expect the performance change to be negligible. Of
course, we have to implement and test to check this.

--
Krishna

May I ask for what you need these double cell shifts?

I know of some crypto routines, but these require even much wider cell sizes.

Another example: in my field pseudo random number generators are common technique.
However PRNGs are closely related to prime numbers and they often require
rotations of sub-cell chunks (linear feedback shift registers).

Krishna Myneni <krishna.myneni@ccreweb.org> writes:
>On 3/27/24 13:46, Anton Ertl wrote:
>> You could point out that the extra cost of the check is only incurred
>> for shifts with non-constant shift amounts, and if you could provide
>> data on the frequency of constant and non-constant shift amounts, this
>> might help convince system implementors.

Here's some data about the occurences in the Gforth image:

Non-constant shift amount:
2 lshift
1 rshift
0 arshift

Constant shift amount:
18 lit lshift
41 lit rshift
0 lit arshift

Produced by inserting superinstructions for the constant shifts,
rebuilding Gforth, and then

gforth-fast --ss-states=0 --print-prims -e bye

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: https://forth-standard.org/
EuroForth 2023: https://euro.theforth.net/2023

On 28/03/2024 2:44 am, Krishna Myneni wrote:
> On 3/27/24 08:57, dxf wrote:
>> On 27/03/2024 10:26 pm, Ruvim wrote:
>>> On 2024-03-27 04:57, Krishna Myneni wrote:
>>> [...]
>>>> We shouldn't have an ambiguous condition here because of some idiosyncratic behavior of the SHL instruction!
>>>>
>>>> u 64 LSHIFT should be zero on all systems with cell sizes up to 64 bits.
>>>
>>> Ideally — yes.
>>>
>>> My rationale (see [1]) is that for any `x` and `u`, the result of a single shift of `x` by `u` bits should always be equivalent to `u` sequential shifts by 1 bit.
>>>
>>> But neither the standard nor implementations follow this idea.
>>
>> The same occurred with 2/ and 2 / .  Those who saw Forth as a language wanted
>> consistent results; whereas those who saw Forth as a toolkit said give us what
>> the hardware provides.
>>
>
> If one needs the machine shift instructions, they should be using the Forth assembler to write the word in which it is needed. The language specification has no justification (that I can see) for undefined behavior for the LSHIFT and RSHIFT instructions.

Some 40 years ago Intel told their customers there's no justification for shifting
a full cell of bits. ANS told the same thing to forthers.

On 3/28/24 03:06, minforth wrote:
> May I ask for what you need these double cell shifts?
>

I'm interested in writing a portable IEEE 754 quad precision arithmetic
library in Forth. The significands are 113 bits long, with implied bit
included. To perform addition or subtraction between two quad precision
numbers, the two significands have to be aligned using the difference in
their base 2 exponents (15 bit exponents). This requires a relative
shift of the two significands across a 128-bit representation of the two
numbers being added/subtracted. On a 64-bit system, we can use double
cell shifts to accomplish this.

> I know of some crypto routines, but these require even much wider cell
> sizes.
>
> Another example: in my field pseudo random number generators are common
> technique.
> However PRNGs are closely related to prime numbers and they often require
> rotations of sub-cell chunks (linear feedback shift registers).

I'm sure there are a lot of other uses that I don't know about. Shifts
registers came up during our previous discussion on SHA512 implementations.

--
Krishna

On 3/28/24 06:29, dxf wrote:
> On 28/03/2024 2:44 am, Krishna Myneni wrote:
>> On 3/27/24 08:57, dxf wrote:
>>> On 27/03/2024 10:26 pm, Ruvim wrote:
>>>> On 2024-03-27 04:57, Krishna Myneni wrote:
>>>> [...]
>>>>> We shouldn't have an ambiguous condition here because of some idiosyncratic behavior of the SHL instruction!
>>>>>
>>>>> u 64 LSHIFT should be zero on all systems with cell sizes up to 64 bits.
>>>>
>>>> Ideally — yes.
>>>>
>>>> My rationale (see [1]) is that for any `x` and `u`, the result of a single shift of `x` by `u` bits should always be equivalent to `u` sequential shifts by 1 bit.
>>>>
>>>> But neither the standard nor implementations follow this idea.
>>>
>>> The same occurred with 2/ and 2 / .  Those who saw Forth as a language wanted
>>> consistent results; whereas those who saw Forth as a toolkit said give us what
>>> the hardware provides.
>>>
>>
>> If one needs the machine shift instructions, they should be using the Forth assembler to write the word in which it is needed. The language specification has no justification (that I can see) for undefined behavior for the LSHIFT and RSHIFT instructions.
>
> Some 40 years ago Intel told their customers there's no justification for shifting
> a full cell of bits. ANS told the same thing to forthers.
>
>

This really isn't an issue with the processor design -- they're under
more severe constraints in what they can put in the hardware. The
desired behavior can be achieved in software.

When I first started programming in Forth, I appreciated the fact that
it was close to the hardware. As processor speed and memory size and the
complexity of my programs grew, and the need to share them as well, the
cleanliness and portability of the language became more important.

--
Krishna

Krishna Myneni wrote:

> On 3/28/24 03:06, minforth wrote:
>> May I ask for what you need these double cell shifts?
>>

> I'm interested in writing a portable IEEE 754 quad precision arithmetic
> library in Forth.

Respect! Scaling is a basic fp operation indeed.

You can test against libquadmath. For inspiration, browsing its source code
might be of interest:
https://codebrowser.dev/glibc/glibc/sysdeps/ieee754/float128/