|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 1044-1045 out of 1137
Modern Operating Systems by Herbert Bos and Andrew...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf-M ODERN O PERATING S YSTEMS
Modern Operating Systems by Herbert...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf-M ODERN O PERATING S YSTEMS
Page 1044
SEC. 12.4
PERFORMANCE
1013
obvious procedure is given in Fig. 12-7(a).
It loops over the bits in a byte, count-
ing them one at a time.
It is pretty simple and straightforward.
#define BYTE
SIZE 8
/* A byte contains 8 bits */
int bit
count(int byte)
{
/
*
Count the bits in a byte.
*
/
int i, count = 0;
for (i = 0; i < BYTE
SIZE; i++)
/
*
loop over the bits in a byte
*
/
if ((byte >> i) & 1) count++;
/
*
if this bit is a 1, add to count
*
/
return(count);
/
*
return sum
*
/
}
(a)
/
*
Macro to add up the bits in a byte and return the sum.
*
/
#define bit
count(b) ((b&1) + ((b>>1)&1) + ((b>>2)&1) + ((b>>3)&1) + \
((b>>4)&1) + ((b>>5)&1) + ((b>>6)&1) + ((b>>7)&1))
(b)
/
*
Macro to look up the bit count in a table.
*
/
char bits[256] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, ...};
#define bit
count(b) (int) bits[b]
(c)
Figure 12-7.
(a) A procedure for counting bits in a byte. (b) A macro to count
the bits.
(c) A macro that counts bits by table lookup.
This procedure has two sources of inefficiency. First, it must be called, stack
space must be allocated for it, and it must return. Every procedure call has this
overhead. Second, it contains a loop, and there is always some overhead associ-
ated with a loop.
A completely different approach is to use the macro of Fig. 12-7(b). It is an
inline expression that computes the sum of the bits by successively shifting the arg-
ument, masking out everything but the low-order bit, and adding up the eight
terms. The macro is hardly a work of art, but it appears in the code only once.
When the macro is called, for example, by
sum = bit
count(table[i]);
the macro call looks identical to the call of the procedure. Thus, other than one
somewhat messy definition, the code does not look any worse in the macro case
than in the procedure case, but it is much more efficient since it eliminates both the
procedure-call overhead and the loop overhead.
We can take this example one step further. Why compute the bit count at all?
Why not look it up in a table?
After all, there are only 256 different bytes, each
with a unique value between 0 and 8.
We can declare a 256-entry table,
bits
, with
each entry initialized (at compile time) to the bit count corresponding to that byte
Page 1045
1014
OPERATING SYSTEM DESIGN
CHAP. 12
value. With this approach no computation at all is needed at run time, just one
indexing operation.
A macro to do the job is given in Fig. 12-7(c).
This is a clear example of trading computation time against memory. However,
we could go still further.
If the bit counts for whole 32-bit words are needed, using
our
bit
count
macro, we need to perform four lookups per word. If we expand the
table to 65,536 entries, we can suffice with two lookups per word, at the price of a
much bigger table.
Looking answers up in tables can also be used in other ways. Anwell-known
image-compression technique, GIF, uses table lookup to encode 24-bit RGB pixels.
However, GIF only works on images with 256 or fewer colors.
For each image to
be compressed, a palette of 256 entries is constructed, each entry containing one
24-bit RGB value. The compressed image then consists of an 8-bit index for each
pixel instead of a 24-bit color value, a gain of a factor of three. This idea is illus-
trated for a 4
×
4 section of an image in Fig. 12-8. The original compressed image
is shown in Fig. 12-8(a). Each value is a 24-bit value, with 8 bits for the intensity
of red, green, and blue, respectively. The GIF image is shown in Fig. 12-8(b).
Each value is an 8-bit index into the color palette. The color palette is stored as part
of the image file, and is shown in Fig. 12-8(c). Actually, there is more to GIF, but
the core idea is table lookup.
3,8,13 3,8,13
3,8,13 3,8,13
26,4,9 90,2,6
4,19,20
4,6,9
4,6,9 10,30,8
5,8,1
22,2,0
10,11,5 4,2,17 88,4,3 66,4,43
7
7
7
7
2
6
3
4
4
5
10
0
8
9
2
11
11
10
1
6
7
8
5
0
9
2
3
4
8 Bits
24 Bits
24 Bits
(b)
(c)
(a)
22,2,0
26,4,9
5,8,1
10,30,8
4,6,9
4,19,20
90,2,6
66,4,43
88,4,3
4,2,17
10,11,5
3,8,13
Figure 12-8.
(a) Part of an uncompressed image with 24 bits per pixel. (b) The
same part compressed with GIF, with 8 bits per pixel. (c) The color palette.
There is another way to reduce image size, and it illustrates a different trade-
off. PostScript is a programming language that can be used to describe images.
(Actually, any programming language can describe images, but PostScript is tuned
for this purpose.)
Many printers have a PostScript interpreter built into them to be
able to run PostScript programs sent to them.
Ace your assessments! Get Better Grades
Browse thousands of Study Materials & Solutions from your Favorite Schools
Concordia University
Concordia_University
School:
Operating_Systems
Course:
Great resource for chem class. Had all the past labs and assignments
Leland P.
Santa Clara University
Introducing Study Plan
Using AI Tools to Help you understand and remember your course concepts better and faster than any other resource.
Find the best videos to learn every concept in that course from Youtube and Tiktok without searching.
Save All Relavent Videos & Materials and access anytime and anywhere
Prepare Smart and Guarantee better grades
Know more
Students also viewed documents
lab 18.docx
lab_18.docx
Course
Course
3
Module5QuizSTA2023.d...
Module5QuizSTA2023.docx.docx
Course
Course
10
Week 7 Test Math302....
Week_7_Test_Math302.docx.docx
Course
Course
30
Chapter 1 Assigment ...
Chapter_1_Assigment_Questions.docx.docx
Course
Course
5
Week 4 tests.docx.do...
Week_4_tests.docx.docx
Course
Course
23
Week 6 tests.docx.do...
Week_6_tests.docx.docx
Course
Course
106
