bit-shifting and ANDing(masking)

Are you new to 6502, NES, or even programming in general? Post any of your questions here. Remember - the only dumb question is the question that remains unasked.

Moderator: Moderators

User avatar
Laserbeak43
Posts: 188
Joined: Fri Sep 21, 2007 4:31 pm
Contact:

Post by Laserbeak43 »

Disch wrote:
I must stress again, though, that AND can only be used in this way when you want to mod by a power-of-2 value. The reason for this is because there can't be "gaps" in the bits you're ANDing. For an example:

$17 mod $0A = $03
because:
$17 - (($17 / $0A) * $0A) = $03
i tried that expresion in PCalc and it played dead "#17 - ( ( #17 / #0A ) * #0A )"
got no result. (#denotes hex in PCalc, according to the instructions)
is that expresion the modulo formula or something?
i understand modulo(i thought i did) and have used it plenty of times in programming and dataflow applications(i don't want you guys to type something that might not be necessary) so masking is just a fancy name for 1 if 1==1(ANDing)?
User avatar
Laserbeak43
Posts: 188
Joined: Fri Sep 21, 2007 4:31 pm
Contact:

Post by Laserbeak43 »

blargg wrote:Think of the equivalent in decimal. You want to get the ones digit of a value. So you divide by 10 and take the remainder. Another way is to keep only the last digit.

1234 / 10 gives remainder of 4
0004 there's the 4

If you want to find the remainder after 100, keep the last 2 digits

1234 / 100 gives remainder of 34
0034 there's the 34

If you instead wanted the remainder after dividing by 9, you wouldn't be able to use this shortcut. So with base 10, you can use it only if your divisor is a power of 10. With base 2, you can use it only if your divisor is a power of 2.
ahh that's a good way to look at it. ease on the brain. man i've been a lazy thinker ever since i've moved to this state :)
User avatar
jargon
B&: This is not your blog
Posts: 208
Joined: Fri Dec 07, 2007 11:40 pm
Location: 480/85260
Contact:

Post by jargon »

EOR is the same as XOR,

it means exclusive or.

perhaps this chart i frickin had to REMAKE DUE TO LOSING THE ORIGINAL FILE....

will assist you :)

Timothy Robert Keal's Boolean Beakers Poster

:wink:

i remade it using GIMP 2.2.17

the original version which is now lost to the ages i had made using PhotoShop.

btw as i mentioned elsewhere in this board:

On most systems:

Code: Select all

Logical Input: NULL is zero and Identity is non-zero.
Logical Output: NULL is zero and Identity is 1.
However in BASIC-A, GW-BASIC, Quick BASIC, and Visual Basic(?):

Code: Select all

Logical Input: NULL is zero and Identity is non-zero.
Logical Output: NULL is zero and Identity is all bits set.
Bitwise works the same on all systems for integers:

Code: Select all

Each bit offset is paired individually.
Bitwise Input: Either the bit in each input mask is off (NULL) or on (Identity).
Bitwise Output: Either the bit in the output mask is off (NULL) or on (Identity).
Bitwise however when using IEEE Floating Precision Values does not exist on nearly all systems, at-least not natively.

Using bitwise operations on IEEE Floating Precision Values generally is a bad idea, as some combination of bits will corrupt the encoding.

:lol:

By the way, the chart I made illustrates examples using *Bitwise* Boolean Operations in the programming language 'C'.
Cheers,
Timothy Robert Keal alias jargon

Image
Miser's House Anthology Project
User avatar
blargg
Posts: 3717
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Post by blargg »

I'm not understanding your boolean logic poster at all. Can you explain it?
User avatar
jargon
B&: This is not your blog
Posts: 208
Joined: Fri Dec 07, 2007 11:40 pm
Location: 480/85260
Contact:

Post by jargon »

%0000 thru %1111 is the binary truth table for each boolean operation.

NULL is FALSE
Identity is TRUE.

the water in the beaker is neither a nor b (%0001)
the orange represents input b. (%0010)
the apple represents input a. (%0100)
the purple overlap between the apple and orange is %1000 in the truth table.

a is %1100 when including the overlap and a in the venn diagram.
notice in a beaker of only water and an apple this is %10
in a beaker of only water and an orange this is %10 too.

notice with evey added fruit (circle) into the venn diagram the amount of digits in the binary mask doubles and all existing bits are repeated next to itself once more.

so %0, %00, %0000 are all FALSE,
and %1, %11, %1111 are all TRUE.

%10 and %1100 are both a
and %01 and %0011 are both not a.

likewise %1100 is a while %1010 is b

likewhise %0100 is just a, while %0010 is just b

also %1000 is both a and b, but not one or the other by themself.


the result of the logic operand is simply ((%mask >> %b) >> (%a<<1)) & %1

where a and b are either one or zero. each

with bitwise operations you perform that using each coupling of the bits for a,b outputting to the same bit offset.

this expands to:
%11110000 which is a for 3 inputs
%11001100 which is b for 3 inputs

also note:
%11001010 which is c for 3 inputs

for 3 inputs it goes:

Code: Select all

high bit: 2 to power 7 (128): all a,b,c
2 to 6 (64): both a,b
2 to 5 (32): both a,c
2 to 4 (16): just a
2 to 3 (8): both b,c
2 to 2 (4): just b
2 to 1 (2): just c
low bit: 2 to power 0 (1): none of a,b,c
this also expands to %111111110000000 which is a for 4 inputs

and so on.

it follows a very predictable pattern of permutations.

if you dump all the operations in order, counting values for last input to first input (a), it acts as a perfect clock counter.

for example:

%0000 thru %1111

dumps as %0 thru %11111111

basically adds the dimension c.

you can recurse this once more in order to add the dimension d. (%0 thru %1111111111111111)

and so on.

hope this helps blargg. :)

that is basically the grand unified ring theory of boolean logic in a nutshell.

%0000 thru %1111 basically map to a logic cube, that is a hypercube with each bit as an axis, each segment being 1 bit in length.

false/true is basically a one bit long line segment. being a beaker either with or without water.

false,!a,a,true is basically a square with one bit long line segments. being a beaker either with or without water, with or without an apple.

my poster shows 16 possibilities, and 16 operations has 4 bit truth tables, that being a venn diagram of two overlapping circles master card logo style, of which produces a cube centered in another cube with all nearest vertices connected of which each vertice a beaker containing water or not containing water, containing a partial apple or not containing a partial apple, containing a partial orange or not containing a partial orange, or containing a merged apple and orange or not containing a merged apple and orange, of which each segment is 1 bit long, for a total of 16 vertices and 32 segments ;) each neighbor vertice is only different by a single bit in its truth table. :D

i came up with a c code generator for each truth table set called Seles in 2002, using this permutation ring theory i call Morsyl.

however Seles got corrupted and no longer works.

i attempted to use Seles to reverse engineer the S-DD1 conversions between input and output for Star Ocean and Street Fighter Alpha 2, but the only existing dumps from Seles are for Star Ocean, and only contain the final output in each part of the dump.

it should have dawned on me that S-DD1 had to have used barrel shifting due to the massive size of the dumps.

my final goal was to combine the two models it produced in order to spawn a common conversion for the two games, however the emulator itself if compiled, would have been uncountably larger than the zSNES emulator, the star ocean/street fighter alpha 2 S-DD1 output, and the star ocean/street fighter alpha 2 roms combined. :roll:

it would prolly have compiled as a binary larger than the entire storage space of all of the net at the time.
Cheers,
Timothy Robert Keal alias jargon

Image
Miser's House Anthology Project
User avatar
Laserbeak43
Posts: 188
Joined: Fri Sep 21, 2007 4:31 pm
Contact:

Post by Laserbeak43 »

ok,
so i've been messing around with 6502 Simulator and decided to do some shifting and masking practice(it's been a while)

and i'm getting some results that don't look right, when i asked someone on #nesdev about it, he said it was wrong too.

Code: Select all

//code
;
; Test shifting
;
 
	.ORG $200
 
 
	LDA #$F0
	STA no1
	LSR no1
	LDA no1
 
	BRK
 
no1:	.DB $00
 
 
//result
0200  A9 F0     LDA #$F0       A:00 X:00 Y:00 F:20 S:1ff 
0202  8D 0D 02  STA $020D      A:f0 X:00 Y:00 F:a0 S:1ff 
0205  4E 0D 02  LSR $020D      A:f0 X:00 Y:00 F:a0 S:1ff 
0208  AD 0D 02  LDA $020D      A:f0 X:00 Y:00 F:20 S:1ff 
020B  00        .DB $00        A:78 X:00 Y:00 F:20 S:1ff
any input would be greatly appreciated
Noob sticky!!
Please document this part of the NESdevWiki!! XD
YOU NEED A RETROMACHINESHOP!!
User avatar
Laserbeak43
Posts: 188
Joined: Fri Sep 21, 2007 4:31 pm
Contact:

Post by Laserbeak43 »

Hmm, maybe it was my sintax or it was right..

Code: Select all

//code
;
; Test shifting
;
 
	.ORG $200
 
 
	LDA #$F0
	LSR 
	STA no1
 
	BRK
 
no1:	.DB $00
 
//result
0200  A9 F0     LDA #$F0       A:00 X:00 Y:00 F:20 S:1ff 
0202  4A        LSR            A:f0 X:00 Y:00 F:a0 S:1ff 
0203  8D 08 02  STA $0208      A:78 X:00 Y:00 F:20 S:1ff 
0206  00        .DB $00        A:78 X:00 Y:00 F:20 S:1ff
Noob sticky!!
Please document this part of the NESdevWiki!! XD
YOU NEED A RETROMACHINESHOP!!
User avatar
blargg
Posts: 3717
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Post by blargg »

Both are correct. $F0 = %11110000. $78 = %01111000. LSR shifts bits right and fills the left bit with 0. BTW, you don't need to store A at all, just do LDA #$F0 then LSR, and look at the value of A afterwards.
User avatar
Laserbeak43
Posts: 188
Joined: Fri Sep 21, 2007 4:31 pm
Contact:

Post by Laserbeak43 »

blargg wrote:Both are correct. $F0 = %11110000. $78 = %01111000. LSR shifts bits right and fills the left bit with 0. BTW, you don't need to store A at all, just do LDA #$F0 then LSR, and look at the value of A afterwards.
hmm it seems that it just took longer for the operation to affect the accumulator with the extra stuff in there.

thanks :)
Noob sticky!!
Please document this part of the NESdevWiki!! XD
YOU NEED A RETROMACHINESHOP!!
User avatar
blargg
Posts: 3717
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Post by blargg »

hmm it seems that it just took longer for the operation to affect the accumulator with the extra stuff in there.
Nope, look more closely. The register values shown after the instruction are BEFORE the instruction executes, not after. Look at the LDA #$F0 for example.
User avatar
Laserbeak43
Posts: 188
Joined: Fri Sep 21, 2007 4:31 pm
Contact:

Post by Laserbeak43 »

blargg wrote:
hmm it seems that it just took longer for the operation to affect the accumulator with the extra stuff in there.
Nope, look more closely. The register values shown after the instruction are BEFORE the instruction executes, not after. Look at the LDA #$F0 for example.
that's my point. in this post's code, the effects of the LSR don't seem to happen until 2 more lines of code
Noob sticky!!
Please document this part of the NESdevWiki!! XD
YOU NEED A RETROMACHINESHOP!!
User avatar
blargg
Posts: 3717
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Post by blargg »

Laserbeak43 wrote:
blargg wrote:
hmm it seems that it just took longer for the operation to affect the accumulator with the extra stuff in there.
Nope, look more closely. The register values shown after the instruction are BEFORE the instruction executes, not after. Look at the LDA #$F0 for example.
that's my point. in this post's code, the effects of the LSR don't seem to happen until 2 more lines of code
In that post, your are LSRing a byte in memory, so the effect will never show in the register display on the right until you load it into a register. Isn't this documented anywhere?
User avatar
Laserbeak43
Posts: 188
Joined: Fri Sep 21, 2007 4:31 pm
Contact:

Post by Laserbeak43 »

i dunno, i'm slow and only truly learn with practice :D
Noob sticky!!
Please document this part of the NESdevWiki!! XD
YOU NEED A RETROMACHINESHOP!!
User avatar
Laserbeak43
Posts: 188
Joined: Fri Sep 21, 2007 4:31 pm
Contact:

Post by Laserbeak43 »

i have no idea why i made this so complicated. after this thread ended i left with some understanding, but when i was asked to do and masking on the board the other day it really clicked, and I imediately though of nesdev and became so embarrased. so i thought i'd come here and make fun of myself. wow i can't believe i made such a big deal about it. it's probably me being stubborn insisting that it be harder than it is....
Noob sticky!!
Please document this part of the NESdevWiki!! XD
YOU NEED A RETROMACHINESHOP!!
Celius
Posts: 2159
Joined: Sun Jun 05, 2005 2:04 pm
Location: Minneapolis, Minnesota, United States
Contact:

Post by Celius »

Oh god, if only you could've seen it when I first came here. I've actually read some of my old topics and I had to stop because I was so embarrassed at my attitude/tone. I made things way more complicated than they needed to be. I give one big apology and a thank you to those who dealt with me during that time =). I'm surprised I wasn't banned! XD
Post Reply