Unit 2.4 -- Bit operations
PROG
PED
to learn about bit-level operations
Concept
We can access individual bits of words by using
shift right and left logical
and
or
exclusive or
Convention
bit 0 (on the left) most significant
SF
bit-by-bit binary logical operations
N regA,memory-address
NR regA,regB
regA = regA "and" memory-address
regA = regA "and" regB
O regA,memory-address
OR regA,regB
regA = regA "or" memory-address
regA = regA "or" regB
X regA,memory-address
XR regA,regB
regA = regA "x-or" memory-address
regB = regA "x-or" regB
A B A "and" B A "or" B A "x-or" B
0 0 0 0 0
0 1 0 1 1
1 0 0 1 1
1 1 1 1 0
Shift Instructions
SRL regA,constant
regA is shifted to the right by "constant"
SLL regA,constant
regA is shifted to the left by "constant"
X'xxxxxxxx'
hex constant corresponding to one word. x= a hex digit
To force allignment, (starting address divisible by four)
DS 0F
Template to move bits numbered x to y of memA to
bits numbered c to d of memB
x-y+1 equal to c-d+1 -- number of bits to be moved
Steps
1) load memA into regA
2) zero out all elements of regA except those between
positions x and y
3) load memB into regB
4) zero out all elements of regB in positions C to D
5) shift regA left or right so that bit A of regA lines up
with bitC of regB
6) add regA to regB
L regA,memA
N regA,mask1
L regB,memB
N regB,mask2
SRL regA,c-x (if x is less than c)
OR
SLL regA,x-c (if x is greater than c c)
OR regB.regA
ST regB,memB
special case, if c-x >15 then have
SRL regA,15
SRL regA,c-x-15
likewise, if x-c >15
SLL regA,15
SLL regA,c-x-15
mask1 <- mask with only bits x to y on
mask2 <- mask with all bints on except those from c to d
75.html
Unit 2.4 Bit String Operations
As you know, a full word (the contents of a register)
consists of 32 bits.
One of the major uses of ASSEMBLER are those cases where it
is necessary to manipulate (test or set) the individual bits
of a word.
There are two possibilities:
1. We want to set, test or mask out specific bits of a
given word. The numbers of the bits to be set are
constants.
We can do these operations with a single instruction.
2. We want to do something to variable bits. We also may
want to perform some operation on all the bits.
We have to go through the full word, one bit at a time.
We can go through all the bits starting at the left-
most bit. In this case, we get to each successive bit
by shifting left.
Or, we can go through the full word starting at the
right-most bit. In this case, we get to each
successive bit by shifting right.
We will be able to discuss this application after we
learn about looping.
There are many times when it is necessary to operate at a
bit-level rather than talk about such entities as characters
or integers. Working on a bit-level is a major application
of Assembly Language.
Assembly Language is used to write device drivers. Device
drivers are programs that interface between an operating
system and a physical device. If you were implied by Connor
Peripherals and they came out with a new disk drive, they
would hire an Assembly Language programmer such as yourself
to write a device driver. If this disk were designed to be
used with IBM PC's such as the ones you used in CS201, they
would want an MS-DOS device driver. Your program would send
various control words to it that would turn it on, find
various sectors, etc. One bit of this control word might
indicate that the operation was a "read" fro the disk.
Another bit might indicate whech side of the disk was being
looked at, etc. When the operation was finished, your
program could inspect a word to indicate whether there was
an I/O error. A particular bit or bits of that word would
indicate the error-status.
Another application is the FAT table in operating systems
such as MS-DOS. FAT stands for File Allocation Table. A
disk drive or diskette contains several sectors. A file
will take up one or more these sectors. The FAT will tell
which sectors have been allocated and which sectors are
free. The FAT is a collection of bits. That is there are
several words arranged contiguously and the words of all of
these form an array. There is one bit for each sector. The
bit for the sector is on when the sector is available.
Otherwise, the bit is off indicating that the sector is in
use and not available for another file. When a file grows
or a new one is created, it becomes necessary to find an
empty sector. The operating system will then search the
FAT, searching for an empty bit.
Another application is the compression of data structures.
I worked in a statistical application where we had 50,000
records. EAch record corresponded to a survey filled out by
an engineer. The engineer provided such information as
their last several jobs, their major when in college, their
highest degree (associates, bacheslors, masters, Ph.D.,
etc.), their job function (management, sales, technical,
etc.), their race and whether they were a U.S. citizen.
Each of these could be kept in a single integer. That would
be the simplest solution from a programming point of view.
But, to save space, many of these data items could kept in a
few bits. The citizenship status could be kept in a single
bit. A person is either a citizen or not. The race could
be kept in three bits. There are only five or so races that
we record. Thus the race could be encoded in a number
between 0 and 7. This could fit in three bits. Likewise,
we might decide to enclode fifteen possible occupations.
These could fit in eight bits. Instead of having a separate
integer for each of these items, we could compress all three
of these things into a single eight-bit byte. One bit would
represent the citizenship status. Another three bits would
represent the race. And four bits would contain the
occupational status. This would be a saving of 11 bytes per
case for a total of about 500,000 bytes for the entire
database.
The last application to be discussed is in image processing.
A black and white image such as that from a CCD camera or
facsimile machine can be represented as a two-dimensional
array of bits. It is often desired to compress this data
so it takes less space in the machine. Or, if we are
transmitting this data, we wish to spend less time to
transmit the bits. Image data has large areas that are
either all black or all white. Thus instead of sending 100
bits that are zero, we could send the number 100. If the
next 55 bits are one, we could send the number 50. And so
on. At the other end, we could convert this back into an
array of bits.
Before discussing how to perform tasks at a bit-level it is
helpful to establish a convention for numbering the bits.
The left-most bit is bit 0 and the right-most bit is bit 31.
Sometimes, bit 0 is referred to as the "most significant"
bit. This is because it corresponds to the highest power of
two.
Bit 31 is then referred to as the "least significant" bit.
It corresponds with two to the zeroth power which is the
one's place.
It is possible to enter masks with the use of a hexadecimal
constant. For example, the constant X'0000FFFF' would
correspond to bits 16 to 31 on. Bits 0 to 15 would be off.
One could also write =X'0000FFFF' as a literal constant.
Let's look at the first case, masking off or on specific
bits or testing them.
There are four instructions that can be used:
and N regA,memory-address
NR regA,regB
sets each bit of regA to one if the corresponding bits of
regA and the second operand are both on. (See the
transparency for the "truth" table.)
It is used to set a bit unconditionally to zero. We do this
by "and"ing with a constant that is zero wherever a bit is
to be turned off.
Example: N 3,=X'F3FFFFFF'
Will turn off positions 4 and 5. All other bits remain
unchanged.
or O regA,memory-address
OR regA,regB
sets each bit of regA to one if either one of the
corresponding bits of regA and the second operand are on.
(See transparency for the "truth" table.)
Used to set a bit unconditionally to "one" Apply "Or" with
a constant that is one where a bit is to be turned off.
Example: O 3,=X'0C000000' will turn on positions 4 and 5.
exclusive or X regA,memory-address
XR regA,regB
sets each bit of regA to one if either, but not both, of the
corresponding bits of regA and regB are on. If both of the
correspondings bits are on, or both of the corresponding
bits are off, then the appropriate bit of bit1 will be set
to off. (See transparency for truth table.)
It can be used to toggle a bit, where you put a "one" in
each position to toggle.
"Toggling" a bit means setting it to one, if it was already
zero and setting it to zero otherwise.
Example, if register 3 contained 1800, and we executed:
X 3,=X'0C00'
Register 3 would be 1400.
Before discussing the options to sequentially go through the
bits of a word from right to left or left to right, we must
learn about the shift logical instructions.
SRL regA,constant
stands for Shift Right Logical
shifts the register to the right by a constant number of
positions.
For example if register 2 was X'6666' and we did
SRL 2,1
then register 2 would be X'3333'
SLL regA,constant
shifts the register to the left by a constant.
If Register 2 was X'3333' and we did,
SRL 2,2
Then register 2 would be X'CCCC'
Unfortunately, there is no way to shift a register a
variable number of times in a single instruction. We will
learn how to deal with the situation when there is a
variable that tells us how many times to shift the register
after we discuss how to write loops in Assembly Language.
A frequent operation is to move some collection of bits from
part of one word to another part of a word. I.E., I may ask
you to write the Assembly Language to transfer bits x to y
of one memory location to bits c to d of another memory
location. These may be fields representing a small integer
such as the number of children which is being kept in a bit.
We saw how survey data can be compressed by taking each
question and storing it as a field inside an integer. When
it is time to perform calculations with the quantity, the
data must be extracted and made ready for calculations. For
example, assume that bits 8 to 10 of a word might represent
the number of children. In order to perform calculations,
the data item representing the number of children would have
to be moved to another variable. In addition, we would have
to get the data to the right hand side position so it
represents a number. In other words, we would have to move
positions 8 to 10 of the word of the survey to bits 29 to 31
of the data. The template below provides a general way to
perform such operations. This template moves the bits from
position x to position y in a memory location that we will
refer to as memA. memA will not be changed. The data will
end up in bits c to d of memB. Note, that we won't disturb
any other bits (bits before position c or after position d)
of memB.
We will assume that there are the same number of bits in
positions x to y as from c to d. That is x-y+1 equal to c-
d+1--number of bits to be moved. Remember that this
template will only work if the x,y,c and d are constants.
The steps are:
1) load memA into regA
2) zero out all elements of regA except those between
positions x and y
3) load memB into regB
4) zero out all elements of regB in positions C to D
5) shift regA left or right so that bit A of regA lines up
with bitC of regB
6) or regA to regB
Or in instruction format, we have
1. L regA,memA
2. N regA,mask1
Mask1 is a constant that is set so that bits x to y are
on. All other bits are off
3. L regB,memB
4. N regB,mask2
Mask2 is a constant that is so that bits c to d are
off. All other bits are off. This cleans up the area
(turns to all zeros) the area of the integer to receive
the bit.
5. If x is less than c, that means we must shift to the
right. So, the code is:
SRL regA,c-x
If x is greater than c, that means we must shift to the
left, so the code is:
SLL regA,x-c
There is one special case. Neither the shift right nor
shift left instructions will handle 16 or more bits.
If we have to do a shift of more than sixteen bits in
either direction, we do it with two shifts. The first
does the first sixteen bits worth of shifting. The
second shift nstruction does the rest of the shifting.
That is, if x is less than c and c-x >15, then we write:
SRL regA,15
SRL regA,c-x-15
If x were greater than c and x-c >15, then the two
instructions would be:
SLL regA,15
SLL regA,c-x-15
6. OR regB.regA
7. ST regB,memB
Now, let us look at the sample program. It will put bits 28
to 30 of the memory location, A, into bits 26 to 28 of
memory location B. The test data looks as follows:
A
11110000111100001111000011111010 (the bits in bold faced
will be moved)
B
11111111111111111111111111010000 (the bits in boldface will
be replaced)
MASK1
00000000000000000000000000001110
MASK2
11111111111111111111111111000111
01234567890123456789012345678901 (bit positions)
1111111111122222222233
In this case, looking at our template x is 28, y is 30.
Likewise, c is 26 and d is 28.
memA in our template refers to A and memB refers to B.
Note that MASK1 has only bits 28 to 30 on. Also, note that
MASK2 has bits 26 to 28 off with every other bit on.
Step 1 of the template is in line 9 of the program. Line 10
of our program perform step 2 of the template. Note that in
this program, regA of the template corresponds to 1 and regB
corresponds to 2. Line 11 implements step 3 of the
template. Line 12 of the template implements step 4 of the
template. Since c is 26 and x is 28, we have to use an SLL
instruction. We shift the field two bits to the left since
the place to put the data (in B) is two bits to the left of
where the data will go in B. We now put the data in line
14, corresponding to step 6 of the template. Lastly line 15
implements step 7 of the template.
Let us review what happens when we run this program.
After line 10, we have masked out the 101 that was boldfaced
on the previous page. Note that if we inspect register one,
we would find it says "A" as it hasn't been shifted out of
its original position.
At line 12, we will have loaded B and cleared out bits 26 to
28. We would find "FFFFFFC0" in register 2 after this line.
In line 13, we move the "101" over two spaces to the left.
We would find hex "28" in register 1 after line 13. Line 14
produces the final result, FFFFFFE8.