Rotate left 2 bits (like assembler)

[logiclrd]

Stop trying to cloud the issue, Z!re :-)

Moneo: There are, as you have of course noticed, two distinct implementations of ROL2 in my example. I assume you did not test the assembler version because your original challenge indicated that a solution that did not use assembler was desired.

PEEK and POKE are functions which directly access memory. A computer's memory stores values organized into 8-bit bytes. When you use an INTEGER or LONG, which are 16 and 32 bits wide each, QBASIC is actually using 2 and 4 bytes, respectively, in memory.

System memory is one continuous block of bytes; if you have 32 megabytes of RAM, then you can think of, at least at the hardware level, a giant array with 32 million bytes in it. However, the processor doesn't offer access to the memory in this way.

In real mode, which is the name for the processor mode that QBASIC runs in, memory addresses are not 32-bit indices into that giant array, but are instead formed of two 16-bit values. Memory is divided into "segments" (the first part of the address), and within each segment, 64 kilobytes of memory are accessible through an "offset" (the second part of the address). Complicating the issue, though, is that the segments aren't separate sections of memory. Instead, they overlap at regular 16-byte boundaries. That is to say, segment 0 is the very start of memory, segment 1 starts 16 bytes into memory, segment 2 starts 32 bytes into memory, etc. Thus, a real mode address, which is of the form "segment:offset", actually refers to the byte at offset (segment * 16 + offset). Most bytes of memory have many different segment:offset pairs referring to the same byte.

This may seem like a bit of a pointless organization, but it made the original x86 processors easier for Intel to design. The largest values the processors could store were only 16 bits, so it wasn't actually possible to directly store the address in memory. Nowadays, there are other modes than real mode where 32-bit addresses are possible, but QBASIC was made before those modes were invented. :-)

QBASIC's syntax integrates with this system using DEF SEG and PEEK/POKE. Every variable in QBASIC has a memory address. QBASIC allocates one or more 64 kilobyte chunks of memory in which to put the variables. Each of these chunks corresponds to a certain segment, and this is called the "data segment" (as opposed to the "code segment" where the actual machine code for the program resides). I mentioned that QBASIC can in fact allocate more than one data segment; therefore, to directly access a variable in memory, you need to determine which data segment it is in. You can request this from QBASIC with the VARSEG function; it returns an INTEGER value that refers to the segment containing the variable you pass to it. The other half of the address is the offset into that segment, and you can get that with the VARPTR function. My example uses both of these in order to get the full "real mode" address of the variable passed to the function.

PEEK and POKE, then, read and write individual bytes of memory, completely outside of QBASIC's variable system, but using VARSEG and VARPTR, you can use PEEK and POKE to access variables being managed by QBASIC. There is one minor snag, though, and that is that PEEK and POKE only take the offset part of the address. In order to pair that up with the correct segment, QBASIC keeps track of a "current segment". This is what DEF SEG sets. Thus, when my code does this:

Code:

DEF SEG = VARSEG(a%)
ptr% = VARPTR(a%)
l% = PEEK(ptr%)
h% = PEEK(ptr% + 1)

..it is telling QBASIC "Please find the segment that the variable a% is stored in, and make that the current segment. Then, find the offset of the variable a% and, within that segment, read the two bytes of memory at that location and the location after it."

Since the data type of a% is INTEGER, it is exactly 2 bytes long, so the variables l% and h% are set to the two bytes that represent the INTEGER value passed to the ROL2 function. :-)

As for the actual rotation, that is handled by the two look-up tables that are initialized only once before all calls to ROL2. The shiftLeft%() table stores the value of each byte shifted left 2 bits. The bits shifted off the top end are stripped off, which is the way a "shift" differs from a "rotate". The shiftRight%() table stores the value of each byte shifted right *6* bits. The 6 right-most bits disappear, leaving only those 2 upper bits that get lost in the shiftLeft%() table.

If you had a single byte that you wanted to *rotate* left by 2 bits, then, you could simply look up that byte in both tables, and combine the two results. The shiftLeft%() table would remove the top 2 bits and shift the remaining 6 ones up against the left edge of the byte, and the shiftRight%() table would bring back those 2 bits, aligned to the right end of the table. Here is an example:

Byte value: 93
Bits: 01011101

shiftLeft%(93) = 116 = 01110100
shiftRight%(93) = 1 = 00000001

Then you OR the values together:

01110100 <-- shiftLeft%(93)
00000001 <-- shiftRight%(93)
01110101

This shows how my tables can be combined to rotate a single byte left by 2 bits. If you have a value spread across 2 bytes, the principle is the same, except instead of joining shiftLeft%() and shiftRight%() values from the same byte, you use them for adjacent bytes, so that through shiftLeft%(), the 6 bits of each byte that stay within the byte get moved to the left, and through shiftRight%(), the top 2 bits of each byte get moved into the low 2 bits of the next byte in the value. This is what the POKE statements in ROL2 do:

Code:

POKE ptr%, shiftLeft%(l%) OR shiftRight%(h%)
POKE ptr% + 1, shiftLeft%(h%) OR shiftRight%(l%)

The actual rotation -- the 2 high bits from the left of the 16-bit value ending up at the right end as the 2 low bits -- is the shiftRight%(h%) on the first POKE line.

Does this explain how the function works? :-)