Epsilon: Add arithmetical and logical operations on integers: and, or, xor, etc.

[debrouxl]

The usual logical operations on booleans and integers:

• and;
• or;
• xor;
• not
• optionally shortcuts for e.g. (and followed by not), (or followed by not), (xor followed by not), (and A with not B) and maybe others
  have already been mentioned in #37 and #133 , but AFAICT, they do not have separate a tracking issue yet :)

[bmuessig]

Yes, this would be amazing. Especially, since hexadecimal and binary are already supported as input and output formats.

[joecrop]

I am interested in taking a crack at implementing this, but it needs more definition first. For example:
We can do logical expressions on boolean values:
and(1,1) = 1

We can also do them on Integers:
and(0xFF,0x0F) = 0x0F

But what happens when we do an inverting function of an integer?
not(0x0F) = 0xF0 //would probably be ideal
But because Numworks stores integers in 32-bit "digits" and we have no way of knowing the bit-width of the number, the not operation would look like this:
not(0x0F) = 0xFFFFFFF0

Is this acceptable?

I am wondering if it would be worthwhile to have an extra parameter to the logical operation that tells the calculator the number of bits to operate on. For example:
not(0x0F, 16) = 0xFFF0
would limit the number of bits to invert at 16.

The problem though is if the input is larger than the number of bits, what do you do?
not(0x0F, 1) = undefined

Does anyone have any thoughts on the best way to implement these expressions?

[bmuessig]

The problem though is if the input is larger than the number of bits, what do you do?
not(0x0F, 1) = undefined

I would always truncate it. The not(0x0F, 1) should be equivalent to ~0x0F & ((1 << 1) - 1).

[joecrop]

So maybe the proposal that I could implement would be:

static Integer xor(const Integer &a, const Integer &b, const Integer &num_bits = 32); // x = a ^ b
static Integer xnor(const Integer &a, const Integer &b, const Integer &num_bits = 32); // x = !(a ^ b)
static Integer and(const Integer &a, const Integer &b, const Integer &num_bits = 32); // x = a & b
static Integer nand(const Integer &a, const Integer &b, const Integer &num_bits = 32); //x = !(a & b)
static Integer or(const Integer &a, const Integer &b, const Integer &num_bits = 32); // x = a | b
static Integer nor(const Integer &a, const Integer &b, const Integer &num_bits = 32); // x = !(a | b)
static Integer not(const Integer &a, const Integer &num_bits = 32); // x = !a
static Integer sll(const Integer &a, const Integer &shift, const Integer &num_bits = 32); // x = a << shift, shift left logical
static Integer srl(const Integer &a, const Integer &shift, const Integer &num_bits = 32); // x = a >> shift, shift right logical
static Integer sra(const Integer &a, const Integer &shift, const Integer &num_bits = 32); // x = a >>> shift, shift right arithmetic
static Integer ror(const Integer &a, const Integer &rotate, const Integer &num_bits = 32); // x = (a >> shift) & ((a & 1) << num_bits), rotate right
static Integer bic(const Integer &a, const Integer &b, const Integer &num_bits = 32); // x = (!a & b)
static Integer bit(const Integer &a, const Integer &bit); // (a >> bit) & 1, return the bit-th bit of a
static Integer bclr(const Integer &a, const Integer &bit); // x = a & !(1 << bit), clear tha bit-th bit of a;
static Integer bset(const Integer &a, const Integer &bit); // x = a | (1 << bit), clear tha bit-th bit of a;
static Integer bflp(const Integer &a, const Integer &bit); // x = a ^ (1 << bit), flip the bit-th bit of a.

Where:

1. num_bits will pad the output beyond the input bit widths with the appropriate 1's or 0s depending on the operation
2. If inputs a or b are larger than num_bits, the output is truncated
3. Inputs a and b must be positive, even if bit 31 is a 1, it is still treated as unsigned (and positive)

I would propose an additional function that can help with two's compliment conversion:

// converts an unsigned binary number to it's two-compliment equivalent Integer
// Simply useful to decode binary numbers that are negative
// Examples:
// If argument 1 is positive, the output will be converted to two-s comp (i.e. look at sign bit in MSB)
tc(0xFF, 8) = -1
tc(0x0F, 8) = 15
// if argument 1 is negative, it is always converted to unsigned
tc(-1, 8) = 255
status Integer tc(const Integer &a, const Integer &num_bits);

But there is no easy way to display negative numbers in binary/hex unless we decide to treat them as always 32 bits, which is a bit dangerous because that would mean you can't represent 0xFFFFFFFF as a positive number (ever) if that were the case.

[debrouxl]

A range of 32 bits was already offered by e.g. TI-68k calculators over two decades ago. If you want the implementation of this feature to stand out from the pack, you should probably aim at least for 64-bit integers :)

Double bonus points for "arbitrary" precision integers, but that's (much ?) more work.

[joecrop]

Yes, if we agree on the const Integer &num_bits input for each function, given the current Numworks poincare Integer infrastructure we can support an arbitrary number of bits from 1-1024. It would be hard for the user to read the display with 1024 bits, but nothing prevents this feature and it is relatively easy to implement given I have already written a version of it here: https://github.com/Omega-Numworks/Omega/pull/441.

However, for displaying negative numbers, if we were to choose a default of 64 bit, the display would be cumbersome. So I'm not sure the best way to handle them... unsigned numbers are straightforward though...

[bmuessig]

You could default to 32 or 64 bit signed and have a signed() conversion function, that takes a number and the bit width and extends the twos complement to display it as a negative number.
e.g. signed(255, 8) would yield -1, while signed(120, 8) would still be 120.
This would also allow two‘s complement on arbitrary bit widths that are smaller than the native bit width.

[bmuessig]

On a side note, it would also make sense to have bit shift right (signed and unsigned as in java), as well as bit shift left

[joecrop]

Yes, going from 0xFF to -1 is easy hence my twos_comp(const Integer &a, const Integer &num_bits); proposal. However, it doesn't seem easy to me to go form -1 to 0xFF. Maybe the best way is to do this is to extend/modify Poincare::Integer to have an m_num_bits private variable that can be stored to support this mode. I'll have to see if that is easily achievable.

[joecrop]

On a side note, it would also make sense to have bit shift right (signed and unsigned as in java), as well as bit shift left

Yes, let me add those definitions to my original function definition post.

[debrouxl]

Beyond shifts, rotate right and left are useful: although they can be synthetized from shifts, or and masking, that's needlessly annoying :)

But shift/rotate operations further bring up the usefulness of flags (especially carry and overflow, they already show up in fixed-size add, sub, mul, etc.), and therefore operation such as add with carry, subtract with carry, rotate with carry. If handling those is desired, the design becomes more complex.

[bmuessig]

Yes, going from 0xFF to -1 is easy hence my twos_comp(const Integer &a, const Integer &num_bits); proposal. However, it doesn't seem easy to me to go form -1 to 0xFF. Maybe the best way is to do this is to extend/modify Poincare::Integer to have an m_num_bits private variable that can be stored to support this mode. I'll have to see if that is easily achievable.

You need a trim function, that again takes the number of output bits. However, storing the number of bits with each integer would also solve the issue.

[bmuessig]

I’m certainly not advocating for feature creep, especially given the low amount of resources available, but a bit(x,a) function, that returns the least significant bit a of the number x at a given position would be nice:
return (x >> a) & 1

[joecrop]

I’m certainly not advocating for feature creep, especially given the low amount of resources available, but a bit(x,a) function, that returns the least significant bit a of the number x at a given position would be nice:
return (x >> a) & 1

Sure, easy enough, I'll add it.

[debrouxl]

AFAICT, besides rotates, the "and A with not B" I mentioned in my original description isn't part of your proposal (yet). nand is "not (A and B)", whereas what I suggested yields the bic instruction on an ARM processor, IIRC :)

I'm not aware of any difference between arithmetical shift left and logical shift left: logical shift left works properly for both signed and unsigned numbers.

[bmuessig]

I'm not aware of any difference between arithmetical shift left and logical shift left: logical shift left works properly for both signed and unsigned numbers.

Indeed, there isn't a difference for left shift. For right shift though, the logical shift just shifts the bits, while the arithmetic shift also extends the sign (see e.g. https://www.tutorialspoint.com/Bitwise-right-shift-operator-in-Java).

[joecrop]

AFAICT, besides rotates, the "and A with not B" I mentioned in my original description isn't part of your proposal (yet). nand is "not (A and B)", whereas what I suggested yields the bic instruction on an ARM processor, IIRC :)

I was thinking this would be an acceptable coverage of that: and(A,not(B, 8), 8)
But if you want a dedication function, it is not hard to implement that. Should I add it to the list?
static Integer bic(const Integer &a, const Integer &b, const Integer &num_bits);

I'm not aware of any difference between arithmetical shift left and logical shift left: logical shift left works properly for both signed and unsigned numbers.

You are right, I will remove sla but keep sra. Should I add rotate right?

[bmuessig]

Should I add rotate right?

For consistency, a rotate right should also be included.

By the way, I would recommend shortening the twos_complement function name to something that can be typed more easily, since it will most likely get used quite often. How about tc()?

[joecrop]

By the way, I would recommend shortening the twos_complement function name to something that can be typed more easily, since it will most likely get used quite often. How about tc()?

Sure, I also plan to add a sub-menu to the toolbox to make it easier to recall these.

[debrouxl]

Yes, both rotate right and rotate left are useful, as are the bit test function mentioned by bmuessig, and the bit manipulation functions as shortcuts for combinations of and / or / xor with a shifted (and inverted, in the case of and) mask: bit clear, bit set, bit invert. The 68000 provides these four bit instructions as btst, bclr, bset, bchg.

[joecrop]

Yes, both rotate right and rotate left are useful, as are the bit test function mentioned by bmuessig, and the bit manipulation functions as shortcuts for combinations of and / or / xor with a shifted (and inverted, in the case of and) mask: bit clear, bit set, bit invert. The 68000 provides these four bit instructions as btst, bclr, bset, bchg.

OK, my 68000 instruction set knowledge it a bit rusty... Can you clearly define what you want those functions to do algebraically?

[debrouxl]

• btst a, x: (x >> a) & 1, !!(x & (1 << a)) or an equivalent expression for returning the a-th bit of x;
• bclr a, x: x &= ~(1 << a), clear tha a-th bit of x;
• bset a,x: x |= (1 << a), set the a-th bit of x;
• bchg a,x: x ^= (1 << a), flip the a-th bit of x.

[joecrop]

• btst a, x: (x >> a) & 1, !!(x & (1 << a)) or an equivalent expression for returning the a-th bit of x;
• bclr a, x: x &= ~(1 << a), clear tha a-th bit of x;
• bset a,x: x |= (1 << a), set the a-th bit of x;
• bchg a,x: x ^= (1 << a), flip the a-th bit of x.

Thanks, I think I have them captured. I renamed a couple of them to make them more friendly named for users not familiar with those names. I chose: bit, bclr, bset, bflp. We can discuss these names if they are contentious.

[joecrop]

Before I dive down this path, here's an example for what I plan to implement. Please provide feedback before I start in earnest.

[bmuessig]

Before I dive down this path, here's an example for what I plan to implement. Please provide feedback before I start in earnest.

I like it. Looking forward to use it, when it's implemented :-)

[debrouxl]

From the POV of a user of the calculation app, at least in some cases - such as the one you're showing, definitely, where both arguments are hex constants, but more generally when both arguments are unsigned - the third argument needs to be implicit. It is on the TI-68k and Nspire series, among others :)

[joecrop]

From the POV of a user of the calculation app, at least in some cases - such as the one you're showing, definitely, where both arguments are hex constants, but more generally when both arguments are unsigned - the third argument needs to be implicit. It is on the TI-68k and Nspire series, among others :)

The xor function does not need a num-bits option, but any inverting function will expand 0's, i.e. and, nor, not, etc.. I added num_bits argument to xor for consistency and it can definitely be implicit. But if we need it to be implicit for inverting functions, the implicit value is non-obvious. In Numworks, Integers have a max of 1024 bits in 32 bit chunks (called digits). So the implicit option could have 3 possibilities, off the top of my head:

1. default to boolean (1 bit), integers larger than 1 would be interpreted as 1
2. default to 32 bits, integers larger than 32 would be truncated. <-(TI calcs do this I believe)
3. Set the number bits based on the max digits in a or b. output_bits = 32*max(a.num_digits(),b.num_digits())

[debrouxl]

Sure, the inverting functions are different from the non-inverting functions. I should have been a bit more specific about my previous message applying best to or and xor :)

About these three possibilities, IMO:

• 1: this one is way too restrictive - that is, unless both arguments have explicit boolean type in the user input, in which case the output should have boolean type as well. Not sure operations like (0 or 1) operator (true or false) should be considered valid, though they have understandable meaning, at least to me.
• 2: yes, as I wrote above, the TI-68k series truncates at 32 bits, which is fairly restrictive;
• 3: from a user's POV, I feel it would be the most convenient one, though it might require a bit of documentation.

BTW, on the topic of expanding: it makes me think that zero-extend above bit M to N bits (should probably be named zext, and return the input unchanged if M > N), and sign extend bit M to N bits (sext, I suppose; unchanged if M > N), are missing from your proposal. Synthetizing extend, especially sign extend, using the other base operators is annoying, AFAIK...

With those extend functions available, the third possibility for an implicit argument to the other operators you mentioned would be easier to use from the POV of the user: shortening or widening numbers / masks would be easier. The third argument could be optional for sext and zext as well, and use the third possibility like the other operators.

EDIT: but first of all, and, or, xor and not, for integers (in up to 1024 bits of 32-bit "digits", I think) and booleans. From that foundation, there can be other iterations later :)

[joecrop]

@debrouxl unfortunately in the way Numworks handles numbers, there is no concept of the number of bits, actually, even digits are a relatively loose construct. For example, when you enter "-1" into the calculator, it parses it as Integer(.digit[0]=1, .negative=true). This is super helpful for the symbolic/reduction features (i.e. removing a double negative, etc.). Even when you enter 0x01, the text is parsed and it stores Integer(.digit[0]=1, .negative=false). This is why you never see hex/bin on the right side of the calculator log, because it only knows about the parsed integer.

Therefore, zero-extension (and even sign extension) would be futile because the raw bits are not stored anywhere. Furthermore, we can't somehow be smart and store the number of bits the user has requested to store for a particular number because the right hand side of the calculator app doesn't actually store a data structure, it stores a string that gets parsed to an integer every time you click on it :(. In light of this, we have to effectively do manual truncation for every operation to maintain some fixed number of bits.

The other challenge, if we go with option 3: output_bits = 32*max(a.num_digits(),b.num_digits()), is the question on how to represent signed numbers and overflow. In the TI cals, if you do not(0x00), the calculator returns Integer -1, so the calculator is not only truncating to 32 bits, but also is using 32-bit signed integers. This makes it very easy for them to understand how to convert a negative number to bin/hex as they always truncate to 32 bits. If we allow for scalable bit widths then negative numbers get even more nebulous.

I'm not sure what the best answer here is. But I am definitely sympathetic to TI's decision to fix everything to 32 bit signed...

[bmuessig]

It might make sense to fix it to 64 bit signed, since the 32-bit days are numbered

[joecrop]

The only problem is that 64 bit negative numbers will be overwhelming to display. Here's what they look like:

Even in hex, the LSBs are hidden from view...

[bmuessig]

You are right, 32 bit would make more sense.

[joecrop]

I have been debating this in my mind for the past couple days now. I'm not convinced there is a simple solution here. Here are my concerns:

Scenario 1: Default precision is 32 bits signed, negative numbers are not displayed in hex/bin

• User calls inverting function: not(0x00) = -1
• User now has no choice but to call another function with integer: not(-1) = 0
• User wants to use hex with an arithmetic operation: -1 + 1 = 0
  - Problem: no display of hex/bin for negative numbers

Scenario 2: Default precision is 32 bits signed, negative numbers ARE displayed in hex/bin, no overflow

• User calls inverting function: not(0x00) = 0xFFFFFFFF
• User calls function with hex: not(0xFFFFFFFF) = 0
• User wants to use hex with an arithmetic operation: 0xFFFFFFFF + 1 = 4294967296
  - Problem: eek! hex is converted to unsigned

Scenario 3: Default precision is 32 bits signed, negative numbers ARE displayed in hex/bin (and translated correctly)

• User calls inverting function: not(0x00) = 0xFFFFFFFF
• User wants to use hex with an arithmetic operation: 0xFFFFFFFF + 1 = 0 //hex is truncated to 32 bits
• User wants to use hex with an arithmetic operation that overflows: 0x1FFFFFFFF + 1 = 0
  - Problem: eek! hex is truncated to 32 bits. is this OK?

I am worried that if we choose 32 bits as the default, the following will happen:

1. no hex/bin display for negative numbers
2. HEX/bin display will be limited to 32 bits (not ideal), or
3. HEX/bin will not be interpreted correctly for negative numbers (even worse)

Either tradeoff 2/3 almost seems like a gating factor that will prevent the Numworks Czars from approving the merge request. and tradeoff 1 is far from ideal too...

[joecrop]

Thinking about this further, maybe the best solution today is to just treat everything as unsigned 32-bit by default.
This will:

1. Work with the calculator's native bin/hex conversions
2. Keep all of the math consistent
3. Not support 2's compliment... but maybe that's ok...

Scenario 4:

• User calls inverting function: not(0x00) = 4294967295
• User can see this result in hex and do more inverting operations: not(4294967295) = 0 or not(0xFFFFFFFF) = 0
• User wants to use hex with an arithmetic operation: 0xFFFFFFFF + 1 = 4294967296 // unchecked overflow which is "OK"

Any concerns about just not supporting two's comp? That would make this achievable.

[bmuessig]

Any concerns about just not supporting two's comp? That would make this achievable.

Wouldn't it be possible to just have a single from signed and to signed function that just converts from a rounded Numworks integer to the unsigned representation and vice versa?

[joecrop]

Wouldn't it be possible to just have a single from signed and to signed function that just converts from a rounded Numworks integer to the unsigned representation and vice versa?

Yes, something like this:

// If argument 1 is positive, the output will be converted to two-s comp (i.e. look at sign bit in MSB)
tc(0xFF, 8) = -1
// if argument 1 is negative, it is always converted to unsigned
tc(-1, 8) = 255

So all logic functions are unsigned and once you want to know what a number is as two's comp, just pass it through the tc() function.

[debrouxl]

It's sad that the hex representation for 64-bit numbers doesn't fit in the Additional results dialog. That said, this particular issue looks like it would be fixed by making the dialog wider: the slack space on the left and right of the screen is larger than two characters and a half with spacing.

Yes, making computations unsigned would simplify things :)

[joecrop]

OK, I think we are aligned on a spec. Let me know if there is anything else to adjust.

static Integer xor(const Integer &a, const Integer &b, const Integer &num_bits = 32); // x = a ^ b
static Integer xnor(const Integer &a, const Integer &b, const Integer &num_bits = 32); // x = ~(a ^ b)
static Integer and(const Integer &a, const Integer &b, const Integer &num_bits = 32); // x = a & b
static Integer nand(const Integer &a, const Integer &b, const Integer &num_bits = 32); //x = ~(a & b)
static Integer or(const Integer &a, const Integer &b, const Integer &num_bits = 32); // x = a | b
static Integer nor(const Integer &a, const Integer &b, const Integer &num_bits = 32); // x = ~(a | b)
static Integer not(const Integer &a, const Integer &num_bits = 32); // x = ~a
static Integer sll(const Integer &a, const Integer &shift, const Integer &num_bits = 32); // x = a << shift, shift left logical
static Integer srl(const Integer &a, const Integer &shift, const Integer &num_bits = 32); // x = a >> shift, shift right logical
static Integer sra(const Integer &a, const Integer &shift, const Integer &num_bits = 32); // x = a >>> shift, shift right arithmetic
static Integer ror(const Integer &a, const Integer &rotate, const Integer &num_bits = 32); // x = (a >> shift) & ((a & 1) << num_bits), rotate right
static Integer bic(const Integer &a, const Integer &b, const Integer &num_bits = 32); // x = (a & ~b)
static Integer bit(const Integer &a, const Integer &bit); // (a >> bit) & 1, return the bit-th bit of a
static Integer bclr(const Integer &a, const Integer &bit); // x = a & ~(1 << bit), clear tha bit-th bit of a;
static Integer bset(const Integer &a, const Integer &bit); // x = a | (1 << bit), clear tha bit-th bit of a;
static Integer bflp(const Integer &a, const Integer &bit); // x = a ^ (1 << bit), flip the bit-th bit of a.

Where:

• num_bits will pad the output beyond the input bit widths with the appropriate 1's for inverting functions (i.e. not, nor, nand, etc.)
• If inputs a or b are >= 2^num_bits, the output is truncated
• If num_bits is not provided, it defaults to 32
• Inputs a and b must be positive, even if bit 31 is a 1, it is still treated as unsigned (and positive)

A helper function will be provided to convert between two's compliment representation:

// converts an unsigned binary number to it's two-compliment equivalent Integer
// Simply useful to decode binary numbers that are negative
status Integer tc(const Integer &a, const Integer &num_bits = 32);

// Examples:
// If argument 1 is positive, the output will be converted to two-s comp (i.e. look at sign bit in MSB)
tc(0xFF, 8) = -1
tc(0x0F, 8) = 15
// if argument 1 is negative, it is always converted to unsigned
tc(-1, 8) = 255

[debrouxl]

I still have comments :)

• most of your comments are using ! for not, which would be correct in boolean context, but in integer context, ~ needs to be used;
• xnor, nand and nor are just not(xor), not(and) and not(or), so they're at best low priority, if not superfluous;
• >>> is >> in C/C++. You'll need to cast the operand to signed before performing the shift and cast again back to unsigned. A working formula for asr of uint32_t value by uint32_t count is (b >= 32) ? UINT32_C(0) : (uint32_t)((int32_t)a >> b);; I checked that on x86, modern GCC versions produce a sar instruction;
• the formula in the ror comment is that of a shift which moves the bottom bit to the top, but not a rotate, AFAICT. A working formula for ror of 32-bit balue by 32-bit count is (a >> b) | (a << ((-b) & 31));; I checked that on x86, modern GCC versions produce a ror instruction;
• rotate left is missing, and in the absence of a function returning the bit width, it cannot easily be emulated by rotating right by the appropriate number of bits, unless the whole set of functions only forever handles fixed-width integers. Better adding a rol function IMO. I know (well, I had forgotten, but saw it again when checking the ARM QRC0001) that the ARM ISA only has ror - which is alright when the instruction width is fixed;
• in the ARM ISA, bic is a & ~b. ~a & b is just a bic with reversed operands, but I think that it would be clearer for users to follow the ARM ISA convention ?

[joecrop]

• most of your comments are using ! for not, which would be correct in boolean context, but in integer context, ~ needs to be used;

Of course, I'll change it for clarity

• xnor, nand and nor are just not(xor), not(and) and not(or), so they're at best low priority, if not superfluous;

Perhaps, best to keep it full featured if the effort is low

• >>> is >> in C/C++. You'll need to cast the operand to signed before performing the shift and cast again back to unsigned. A working formula for asr of uint32_t value by uint32_t count is (b >= 32) ? UINT32_C(0) : (uint32_t)((int32_t)a >> b);; I checked that on x86, modern GCC versions produce a sar instruction;

Good to note. Because the function will support arbitrary bit widths, I don't think we can leverage native c++ here. I think the operation will need to look more like this:

for (n=0; n<b; n++) {
   msb = (a & (1 << num_bits)) >> num_bits;
   a = (a >> 1) | (msb << num_bits);
}

• the formula in the ror comment is that of a shift which moves the bottom bit to the top, but not a rotate, AFAICT. A working formula for ror of 32-bit balue by 32-bit count is (a >> b) | (a << ((-b) & 31));; I checked that on x86, modern GCC versions produce a ror instruction;

You are saying the ror instruction moves 4 bits instead of 1 right? As someone who designs data converters, I see value in being able to rotate by an arbitrary amount... If we hard code this to match a processor instructions, are there practical mathematical uses that add value to the calculator other than just emulating a processor?

• rotate left is missing, and in the absence of a function returning the bit width, it cannot easily be emulated by rotating right by the appropriate number of bits, unless the whole set of functions only forever handles fixed-width integers. Better adding a rol function IMO. I know (well, I had forgotten, but saw it again when checking the ARM QRC0001) that the ARM ISA only has ror - which is alright when the instruction width is fixed;

Yes, I think the whole set of functions does only support fixed width integers... and the default would be 32. I fear there might be a detail I am missing with your concern here.

I'm happy to add 'rol', but the same question as above applies, should it be hard coded to a nibble, limiting its functionality outside of processors?

• in the ARM ISA, bic is a & ~b. ~a & b is just a bic with reversed operands, but I think that it would be clearer for users to follow the ARM ISA convention ?

I agree

[debrouxl]

Sorry, I forgot to reply to your comment.

ror by 8 bits and rol by 8 bits are among the right ways to swap the endianness of a 16-bit value. Rotation is also the right way to preserve the background mask in operands of the form VVVVVVVV 11111111 11111111 11111111 when shifting right (arithmetical shift right does the job only if the topmost bit of V), or 11111111 11111111 11111111 VVVVVVVV when shifting left (can't directly insert 1 bits by logical shift left).
Last but not least, multiple other calculator families provide a rotate operation :)

For users' sake, ror and rol should probably not be hard-coded to a nibble if sll, slr and sar aren't.

[joecrop]

For users' sake, ror and rol should probably not be hard-coded to a nibble if sll, slr and sar aren't.

Let me try to interpret your proposal. Is this what you are trying to say?

static Integer ror(const Integer &a, const Integer &rotate, const Integer &num_bits = 32);
where:
 x = (a >> rotate) & ((a & ((2^rotate)-1)) << (num_bits-rotate))

i.e.

a = 0b11111111_00000000
rotate = 8
num_bits = 16
x = 0b00000000_11111111

or

a = 0b11111111_00000000
rotate = 2
num_bits = 16
a = 0b0011111_11000000

If this matches your statements above, then I think we have been talking about the same thing from the begining. Let me know if I a missing a detail.

[debrouxl]

Yes, that's the kind of behaviour I have in mind for ror as well :)

You typo'ed a | as & in the formula, but you'd have noticed it soon anyway when making tests.

[joecrop]

OK,

Now that the spec has firmed up, I have started the easy part... implementation. I have worked though the corner cases dealing with parsing and truncation and have a demo of the basic logic functions (or/nor, xor/xnor, and/nand, not). Enjoy:

https://user-images.githubusercontent.com/3010369/104874316-8111c280-5907-11eb-8159-c1a54932a2f9.mov

If anyone is interested, my development branch is here: https://github.com/joecrop/Omega/tree/binary_arithmetic_functions

[joecrop]

I'm getting very close to finishing. All of the functions we defined have been written with test cases. There;'s just a couple decision points left:

1. It turns out that Epsilon tries to be smart and limit the display of large integers. For example, if you type 2^99 - 1 you will get 2^99 - 1 = 633825300114114700748351602687. However, when you type 2^100 - 1 you get 2^100 - 1 = 2^100 - 1. Without changing this core function, this limits the number of bits for logic operations to 99. (there is also a setting that turns off HEX display when the number is above some smaller number, but that can be easily dialed back up). I find it odd that this limitation does not exist in Omega, it must be some new-ish "feature". What the best way to proceed?
   
   
   
   1. Just limit to 99 max bits?
   
   
   2. Petition Numworks to turn that "feature" back off so more bits can be realized?
   
   
2. I have added toolbox menu items for each of the functions (see screenshot). I would appreciate feedback on the descriptions. (translations appreciated too ;) ). See below:

Logic = "Logic"
LogicalAnd = "a AND b"
LogicalBitClear = "Clear bit number b in a"
LogicalBitFlip = "Flip bit number b in a"
LogicalBitGet = "Get bit number b in a"
LogicalBitSet = "Set bit number b in a"
LogicalBitsClear = "Clear a with bits in b [a AND NOT(b)]"
LogicalNand = "a NAND b"
LogicalNor = "a NOR b"
LogicalNot = "NOT a"
LogicalOr = "a OR b"
LogicalShiftLeft = "Logical shift left [a << s]"
LogicalShiftRightArithmetic = "Arithmetic shift right [a >>> s]"
LogicalShiftRight = "Logical shift right [a >> s]"
LogicalRotateLeft = "Rotate r bits of a to the left"
LogicalRotateRight= "Rotate r bits of a to the left"
LogicalXnor = "a XNOR b"
LogicalXor = "a XOR b"
TwosComplementToBits = "Two's complement equivalent"

[bmuessig]

1. Just limit to 99 max bits

I think everything up to 64 would have worked already, you're fine ;-)

1. translations appreciated too

I can offer a German translation.

[bmuessig]

This would be my take at a German translation of the above strings:

Logic = "Logik"
LogicalAnd = "a AND b"
LogicalBitClear = "Bit b in a löschen"
LogicalBitFlip = "Bit b in a umkehren"
LogicalBitGet = "Bit b aus a lesen"
LogicalBitSet = "Bit b in a setzen"
LogicalBitsClear = "a AND NOT(b)"
LogicalNand = "a NAND b"
LogicalNor = "a NOR b"
LogicalNot = "NOT a"
LogicalOr = "a OR b"
LogicalShiftLeft = "Bitverschiebung nach links [a << s]"
LogicalShiftRightArithmetic = "Arithmetische Verschiebung nach rechts [a >>> s]"
LogicalShiftRight = "Bitverschiebung nach rechts [a >> s]"
LogicalRotateLeft = "Rotieren von a um r Bits nach links"
LogicalRotateRight= "Rotieren von a um r Bits nach rechts"
LogicalXnor = "a XNOR b"
LogicalXor = "a XOR b"
TwosComplementToBits = "Äquivalent im Zweierkomplement"

LogicalRotateRight= "Rotate r bits of a to the left"

I think you meant "Rotate r bits of a to the right".

[debrouxl]

My take at a French translation:

Logic = "Logic"
LogicalAnd = "a AND b"
LogicalBitClear = "Effacer le bit numéro b dans a"
LogicalBitFlip = "Inverser le bit numéro b dans a"
LogicalBitGet = "Obtenir le bit numéro b dans a"
LogicalBitSet = "Allumer le bit numéro b dans a"
LogicalBitsClear = "Effacer a avec les bits de b [a AND NOT(b)]"
LogicalNand = "a NAND b"
LogicalNor = "a NOR b"
LogicalNot = "NOT a"
LogicalOr = "a OR b"
LogicalShiftLeft = "Décalage logique à gauche [a << s]"
LogicalShiftRightArithmetic = "Décalage arithmétique à droite [a >>> s]"
LogicalShiftRight = "Décalage logique à droite [a >> s]"
LogicalRotateLeft = "Rotation de a de r bits vers la gauche"
LogicalRotateRight= "Rotation de a de r bits vers la droite"
LogicalXnor = "a XNOR b"
LogicalXor = "a XOR b"
TwosComplementToBits = "Equivalent en complément à deux"

though I'm not really happy with "allumer" in LogicalBitSet.

[joecrop]

OK, I'll settle for 64 bits max...

Looks like the max string length is 34 characters for these toolbox messages. Can you shorten some of these please? Here's my attempt on the shortened English:

Logic = "Logic"
LogicalAnd = "a AND b"
LogicalBitClear = "Clear bit number b in a"
LogicalBitFlip = "Flip bit number b in a"
LogicalBitGet = "Get bit number b in a"
LogicalBitSet = "Set bit number b in a"
LogicalBitsClear = "Clear a with b [a AND NOT(b)]" //shortened
LogicalNand = "a NAND b"
LogicalNor = "a NOR b"
LogicalNot = "NOT a"
LogicalOr = "a OR b"
LogicalShiftLeft = "Logical shift left [a << s]"
LogicalShiftRightArithmetic = "Arithmetic shift right [a >>> s]"
LogicalShiftRight = "Logical shift right [a >> s]"
LogicalRotateLeft = "Rotate r bits of a to the left"
LogicalRotateRight= "Rotate r bits of a to the right" //corrected
LogicalXnor = "a XNOR b"
LogicalXor = "a XOR b"
TwosComplementToBits = "Two's complement equivalent"

[bmuessig]

Looks like the max string length is 34 characters for these toolbox messages.

Here you go:

Logic = "Logik"
LogicalAnd = "a AND b"
LogicalBitClear = "Bit b in a löschen"
LogicalBitFlip = "Bit b in a umkehren"
LogicalBitGet = "Bit b aus a lesen"
LogicalBitSet = "Bit b in a setzen"
LogicalBitsClear = "a AND NOT(b)"
LogicalNand = "a NAND b"
LogicalNor = "a NOR b"
LogicalNot = "NOT a"
LogicalOr = "a OR b"
LogicalShiftLeft = "Bitverschiebung links von a um s"
LogicalShiftRightArithmetic = "Arithm. Versch. rechts von a um s"
LogicalShiftRight = "Bitverschiebung rechts von a um s"
LogicalRotateLeft = "Rotieren von a um r Bit n. links"
LogicalRotateRight= "Rotieren von a um r Bit n. rechts"
LogicalXnor = "a XNOR b"
LogicalXor = "a XOR b"
TwosComplementToBits = "Äquivalent im Zweierkomplement"

[debrouxl]

Logic = "Logic"
LogicalAnd = "a AND b"
LogicalBitClear = "Effacer le bit numéro b dans a"
LogicalBitFlip = "Inverser le bit numéro b dans a"
LogicalBitGet = "Obtenir le bit numéro b dans a"
LogicalBitSet = "Allumer le bit numéro b dans a"
LogicalBitsClear = "Effacer bits b ds a [a AND NOT(b)]"
LogicalNand = "a NAND b"
LogicalNor = "a NOR b"
LogicalNot = "NOT a"
LogicalOr = "a OR b"
LogicalShiftLeft = "Décalage logique gauche [a << s]"
LogicalShiftRightArithmetic = "Décalage arith. droite [a >>> s]"
LogicalShiftRight = "Décalage logique droite [a >> s]"
LogicalRotateLeft = "Rotation gauche de a par r bits"
LogicalRotateRight= "Rotation droite de a par r bits"
LogicalXnor = "a XNOR b"
LogicalXor = "a XOR b"
TwosComplementToBits = "Equivalent en complément à deux"

Might save a character in all translations by using [a AND NOT b] in LogicalBitsClear. I thought about that because none of the other descriptions have parentheses.

[bmuessig]

Might save a character in all translations by using [a AND NOT b] in LogicalBitsClear. I thought about that because none of the other descriptions have parentheses.

Personally, I find the term easier to understand than the description in this case.

On a side note, I have decided to leave the logic operator names in English. I'm working at a TechEd company and whenever we're dealing with digital logic, we have settled to use the English forms internationally, as many German universities have done the same before us.

[joecrop]

Good to know, I have translated the other languages with google translate. There is one more line that I forgot if you want to provide translations too:

ExplicitNumberOfBits = "Explicit number of bits"

[bmuessig]

ExplicitNumberOfBits = "Explicit number of bits"

Sure, that would be "Explizite Bitbreite".

Good to know, I have translated the other languages with google translate.

I can really recommend deepl.com. It has quite good AI based translation of most European languages and in my comparisons usually does much better than Google Translate.

Thanks for implementing the new functions. I can't wait to hopefully see them merged with an upcoming version.

[debrouxl]

ExplicitNumberOfBits = "Nombre indiqué de bits", I'd say, in that context.

[joecrop]

Hi Guys,

I have created a pull request with all the features we discussed: https://github.com/numworks/epsilon/pull/1756
Can you please review? Most of the Code is copy-paste, but there are two files that contain the key functionality and test cases:

1. poincare/src/integer.cpp
2. poincare/test/logic.cpp

[artaxxx]

Thanks for participating so much in this issue! Some of these features may be useful for high school users. I will think about the list we would like to add, but I think the best first step is to take something basic. For example, the third argument of the functions could be removed. This may be a little too expert and not necessarily necessary (except for the bit rotations but I don't think it will go on the firmware for the first step of this implementation).
I will think about the wording of the name and legend of these functions and their arrangement in the toolbox menu.
See you soon!

[debrouxl]

Removing the third argument makes the functions much less useful in my book :)
And now that the work has been done, it makes little sense to spend extra time removing it.

The list of functions here is already fairly limited. The TI-68k series from 25 years ago, the most familiar calculators to me, and the Nspire series which succeeds these, have and/or/xor, not, rotate (with a second optional argument specifying the direction), shift (ditto). I'm sure giac and everything derived from it has proper functions as well.
This leaves nand/nor/xnor, as well as the bit functions, on the table; the 68000, among others, has bit functions. Without these, one has to resort to simple, but more annoying, operations based on shifts or rotates.

[artaxxx]

But, what is exactly the purpose of having the third argument in and for instance?

[debrouxl]

The implementation uses the third argument to truncate the output to the specified number of bits, which is what I want to occur when and'ing larger values together - such values can be produced easily by not, shifts and rotates - then extract only a subset of the bits :)

I don't think that we want to go through the work of providing everything needed to build a full-blown ALU, with complete flag handling and everything else expected from a well-behaved ALU. However, I think that it's best to provide users better functionality than competitors have been offering users for over two decades.

[artaxxx]

But I have the feeling that it should be a separate function (maybe trunc), right? Maybe we could stay consistent with other languages (operator library in Python for example) for the syntax of this kind of functions.

[joecrop]

I agree that the 3rd argument will add confusion to most anyone that hasn't read the documentation. Here's my comments:

1. The 3rd argument is implicit, you only set it if you need it, otherwise it defaults to 32 bits. So no-one will be burdened by it unless they want it.
2. The and function doesn't need it, but there is no harm in having two and functions: and(a,b) and and(a,b,n). Most people will use the former and the later is there for "advanced" users that want to truncate for free.
3. The toolbox menu only lists the implicit optioned functions, there is a sub-menu for functions that have the explicit num_bits parameter.
   

[Ecco]

An implicit third argument would work, but in general I'm not a big fan of hidden features.

Also, since we also have Python interpreter, we may not need to handle all the weird cases in the Calculation app.

[joecrop]

Also, since we also have Python interpreter, we may not need to handle all the weird cases in the Calculation app.

Can you elaborate on this please? How would python eliminate the problem of the third argument?

Also, I am really hoping there aren't any issues writing this in c++ because it has already been implemented.

[Ecco]

Can you elaborate on this please? How would python eliminate the problem of the third argument?

Well, my point is that Python kinds of eliminate the need for the entire feature altogether:

• It already does bitwise operations
• It's very easy to define additional custom functions for expert users

So the question really is about "what do we want to put in the Calculation app".

Also, I am really hoping there aren't any issues writing this in c++ because it has already been implemented.

Well, not _per se_. I think it makes sense to provide _some_ binary/boolean functions in the Calculation app, but then it's really a compromise.

One problem I can see is that the PR currently adds a lot of code (and results in an additional 32 KB to the firmware), for a feature that I don't think is really critical.

[bmuessig]

One problem I can see is that the PR currently adds a lot of code (and results in an additional 32 KB to the firmware), for a feature that I don't think is really critical.

Considering that, I'd vouch for having only two arguments. If space is this much of a concern, NAND and NOR could also be removed.
However, I'd really like to see the feature become reality, as I am using these all the time and I never found the Python feature to be particularly quick to use on Numworks. I've already done it on another calculator, before I have it ready on Python.

[debrouxl]

bmuessig brings a very important point about usability. Having this kind of basic functionality available in the Calculation app - just like it is on other calculator models, simply put - without having to switch to another app, and back, seems important to me as well.

The weight of the third argument handling could be a lesser contributor to the binary size increase than the weight all of these ExpressionNode-derived classes, I'd have to build the patched version to check. If that holds true, then:

• nand, nor and xnor should go away:
• sll & srl could be folded to a lshift() function, and the sign of the second argument would indicate the direction;
• sra (& therefore the currently nonexistent sla) could become an ashift() function, with the same meaning for the second argument;
• ditto for rorand rol, they'd become a single rotate() function;
• the jury's out on the 4 bit manipulation functions. They're convenient and represent something competitors don't have, which is why I suggested them; however, it's a fact that the Expression-Node derived classes for these four functions represent kilobytes of code+data.

Having to cut down on features because of limited hardware definitely has a fun part, I did my share of that even for the NumWorks calculator, but also an annoying part. "Life is short and Flash is full".

[joecrop]

1) So, off the cuff, it seems like removing 3 functions and merging 2 we are saving 10 of 31 total toolbox functions. So it is likely that we can go from 32k to 20k. Is that good enough? Doesn't seem like it...

2) Removing all of the functions that have a 3rd argument would not be as a significant change as you might think. 60% of the firmware increase is actually from text, the text would get no smaller, so you would be reducing the functions by 40%, which is actually less of a decrease than proposal 1. Plus, all integers would be hard coded to 32 bits :(

[joecrop]

Maybe instead of playing the recursive game of "is this small enough", @Ecco can you advise on what size would be acceptable? Then we can see what features we can squeeze in that limitation.