Screen 02 course builds on the foundation of Screen 01, teaching you how to draw lines and a small feature that generates pseudo-random numbers. Assuming you already have the operating system code from Course 6: Screen 01[1], we will build on it.
1. Points
Now that our screen is working properly, it’s time to create a more practical image, which is a natural progression. It would be even better if we could draw a line between two points on the screen, allowing us to combine these lines to create more complex shapes.
We will try to implement it using assembly code, but initially, we do need to use some other functions to assist. We need a function, which I will call SetPixel, to modify the color of a specified pixel, with inputs provided in registers r0 and r1. If the code we write can draw shapes in any memory, not just on the screen, this will be very useful later, so we first need some control methods for the actual drawing position. I think the best way to achieve this goal is to have a memory segment to store the shape to be drawn. What I should ultimately get is a storage address that typically points to the frame buffer structure from the last frame. We will use this drawing method throughout our code. This way, if we want to draw a different image in another part of our operating system, we can generate a different structured address value while using exactly the same code. For simplicity, we will use another data segment to control the color we are drawing.
To draw more complex shapes, some methods use a shading function instead of a color to draw. Each point can call the shading function to determine what color to draw there.
Copy the following code into a new file named drawing.s.
.section .data
.align 1
foreColour:
.hword 0xFFFF
.align 2
graphicsAddress:
.int 0
.section .text
.globl SetForeColour
SetForeColour:
cmp r0,#0x10000
movhs pc,lr
ldr r1,=foreColour
strh r0,[r1]
mov pc,lr
.globl SetGraphicsAddress
SetGraphicsAddress:
ldr r1,=graphicsAddress
str r0,[r1]
mov pc,lr
This code is what I mentioned above, a pair of functions and their data. We will use them in main.s to control where to draw what content before rendering images.
Our next task is to implement a SetPixel method. It needs to take two parameters, the pixel’s x and y axes, and it should use graphicsAddress and foreColour to precisely control where to draw what image. If you think you can implement this immediately, go ahead; if not, follow the steps we provide and implement it according to the example.
Building a generic method like
SetPixelthat we can build another method on top of is a good idea. But we must ensure this method is fast because we will use it frequently.
graphicsAddress.frameBufferAddress + (x + y * width) * pixelSize)foreColour.The above steps are implemented as follows:
1. Load graphicsAddress.
.globl DrawPixel
DrawPixel:
px .req r0
py .req r1
addr .req r2
ldr addr,=graphicsAddress
ldr addr,[addr]
2. Remember, the width and height are stored at offsets 0 and 4 in the frame buffer. You can refer to frameBuffer.s if necessary.
height .req r3
ldr height,[addr,#4]
sub height,#1
cmp py,height
movhi pc,lr
.unreq height
width .req r3
ldr width,[addr,#0]
sub width,#1
cmp px,width
movhi pc,lr
3. Indeed, this code is specifically for high-color frame buffers because I use a logical left shift operation to calculate the address. You might want to write a function version that doesn’t require a dedicated high-color frame buffer, and remember to update the code for SetForeColour. It may be more complicated to implement.
ldr addr,[addr,#32]
add width,#1
mla px,py,width,px
.unreq width
.unreq py
add addr, px,lsl #1
.unreq px
mla dst,reg1,reg2,reg3multiplies the values in registersreg1andreg2, then adds the result to the value in registerreg3, storing the low 32 bits of the result indst.
4. This is specific to high color.
fore .req r3
ldr fore,=foreColour
ldrh fore,[fore]
5. This is specific to high color.
strh fore,[addr]
.unreq fore
.unreq addr
mov pc,lr
2. Lines
The problem is that drawing lines is not as simple as you might imagine. So far, you must realize that when writing an operating system, almost everything must be done ourselves, and drawing lines is no exception. I suggest you take some time to think about how to draw a line between any two points.
I estimate that most strategies might be to calculate the gradient of the line and draw along it. This seems perfect, but it’s actually a terrible idea. The main problem is that it involves division, which we know is not easy to do in assembly, and keeping track of decimals is also challenging. In fact, there is an algorithm called Bresenham’s algorithm that is excellent for assembly code because it only uses addition, subtraction, and bit-shifting operations.
In our daily programming, we often neglect to optimize operations like division. But operating systems are different; they must be efficient, so we must always focus on how to do things as well as possible.
We start by defining a simple line-drawing algorithm, as shown below:
/* We want to draw a line from (x0,y0) to (x1,y1) using only a function setPixel(x,y), which draws a point at the given (x,y). */ if x1 > x0 then set deltax to x1 - x0 set stepx to +1 otherwise set deltax to x0 - x1 set stepx to -1 end if if y1 > y0 then set deltay to y1 - y0 set stepy to +1 otherwise set deltay to y0 - y1 set stepy to -1 end if if deltax > deltay then set error to 0 until x0 = x1 + stepx setPixel(x0, y0) set error to error + deltax ÷ deltay if error ≥ 0.5 then set y0 to y0 + stepy set error to error - 1 end if set x0 to x0 + stepx repeat otherwise end ifThis algorithm represents what you might imagine. The variable
erroris used to track your distance from the actual line. Each step along the x-axis increases thiserrorvalue, while each step along the y-axis decreases it by one unit.erroris used to measure the distance from the y-axis.While this algorithm is effective, it has a significant problem; clearly, we used decimals to store
error, and we also used division. So, an immediate optimization would be to change the unit oferror. There is no need to store it in specific units, as long as we scale it by the same amount every time we use it. Therefore, we can rewrite this algorithm by simply multiplyingerrorbydeltayin all equations involvingerror, simplifying it. Below only shows the main loop:set error to 0 × deltay until x0 = x1 + stepx setPixel(x0, y0) set error to error + deltax ÷ deltay × deltay if error ≥ 0.5 × deltay then set y0 to y0 + stepy set error to error - 1 × deltay end if set x0 to x0 + stepx repeatIt simplifies to:
set error to 0 until x0 = x1 + stepx setPixel(x0, y0) set error to error + deltax if error × 2 ≥ deltay then set y0 to y0 + stepy set error to error - deltay end if set x0 to x0 + stepx repeatSuddenly, we have a better algorithm. Now, let’s see how to completely eliminate the division operations. It is best to keep the only multiplication by 2, which we know can be achieved by shifting left by one bit! Now, this is very close to Bresenham’s algorithm, but it can be further optimized. Now we have an
ifstatement that leads to two code blocks, one for lines with a larger x difference and the other for lines with a larger y difference. For both types of lines, if examining the code can convert them into a single statement, it is still worth doing.The difficulty lies in the fact that in the first case,
errorvaries with y, while in the second case,errorvaries with x. The solution is to record them simultaneously in one variable, using negativeerrorto represent anerrorin x, and positiveerrorto represent it in y.set error to deltax - deltay until x0 = x1 + stepx or y0 = y1 + stepy setPixel(x0, y0) if error × 2 > -deltay then set x0 to x0 + stepx set error to error - deltay end if if error × 2 < deltax then set y0 to y0 + stepy set error to error + deltax end if repeatYou may need some time to figure it out. At each step, we correctly move in x and y. We do this by checking if moving in the x or y direction decreases the
errorvalue, then we continue to move in that direction.
Bresenham’s algorithm was developed in 1962 by Jack Elton Bresenham when he was 24 years old and pursuing his PhD.
The Bresenham algorithm for drawing lines can be described by the following pseudocode. The following pseudocode is text that just looks a bit like computer instructions, but it allows programmers to genuinely understand the algorithm rather than being machine-readable.
/* We want to draw a line from (x0,y0) to (x1,y1) using only a function setPixel(x,y), which draws a point at the given (x,y). */
if x1 > x0 then
set deltax to x1 - x0
set stepx to +1
otherwise
set deltax to x0 - x1
set stepx to -1
end if
set error to deltax - deltay
until x0 = x1 + stepx or y0 = y1 + stepy
setPixel(x0, y0)
if error × 2 ≥ -deltay then
set x0 to x0 + stepx
set error to error - deltay
end if
if error × 2 ≤ deltax then
set y0 to y0 + stepy
set error to error + deltax
end if
repeat
Unlike the numbered list we are currently using, this algorithm’s representation is more common. See if you can implement it yourself. Below I provide my implementation as a reference.
.globl DrawLine
DrawLine:
push {r4,r5,r6,r7,r8,r9,r10,r11,r12,lr}
x0 .req r9
x1 .req r10
y0 .req r11
y1 .req r12
mov x0,r0
mov x1,r2
mov y0,r1
mov y1,r3
dx .req r4
dyn .req r5 /* Note, we only use -deltay, hence I save its negative value. (thus named dyn)*/
sx .req r6
sy .req r7
err .req r8
cmp x0,x1
subgt dx,x0,x1
movgt sx,#-1
suble dx,x1,x0
movle sx,#1
cmp y0,y1
subgt dyn,y1,y0
movgt sy,#-1
suble dyn,y0,y1
movle sy,#1
add err,dx,dyn
add x1,sx
add y1,sy
pixelLoop$:
teq x0,x1
teqne y0,y1
popeq {r4,r5,r6,r7,r8,r9,r10,r11,r12,pc}
mov r0,x0
mov r1,y0
bl DrawPixel
cmp dyn, err,lsl #1
addle err,dyn
addle x0,sx
cmp dx, err,lsl #1
addge err,dx
addge y0,sy
b pixelLoop$
.unreq x0
.unreq x1
.unreq y0
.unreq y1
.unreq dx
.unreq dyn
.unreq sx
.unreq sy
.unreq err
3. Randomness
So far, we can draw lines. While we can use it to draw images and such (feel free to do so!), I think we should take this opportunity to introduce the concept of randomness in computers. I will do this by choosing a pair of random coordinates and drawing a line to that point from the previous pair using a gradient color. I do this purely because it looks nice.
So, to summarize, how can we generate random numbers? Unfortunately, we do not have some device to generate random numbers (such devices are rare). Therefore, we can only utilize what we have learned so far to somehow invent “random numbers.” You will quickly realize that this is impossible. Various operations always yield defined results; running the same sequence of instructions on the same register will always give the same answer. What we need to deduce is a pseudo-random sequence. This means that the numbers appear random to outsiders, but in reality, they are completely determined. Therefore, we need a formula to generate random numbers. Some might think of some garbage mathematical operations like: 4x2! / 64, which actually produces a low-quality random number. In this example, if x is 0, then the answer will be 0. It seems foolish, and we need to be very careful in choosing a formula that can produce high-quality random numbers.
Hardware random number generators are rarely used in security, as predictable random number sequences may affect the security of certain encryptions.
The method I am going to teach you is called the “Quadratic Congruential Generator.” This is a very good choice because it can be implemented in 5 instructions and can produce a seemingly random sequence of numbers between 0 and 232-1.
Unfortunately, the study of why using so few instructions can produce such a long sequence has far exceeded the scope of this course. But I still encourage those interested to research it. Its entire core lies in the following quadratic equation, where xn is the nth generated random number.
This kind of discussion often seeks a question: what do we call random numbers, anyway? Usually, from a statistical perspective, randomness is: a sequence of numbers that has no obvious patterns or properties that can summarize it.
This equation is subject to the following restrictions:
If you have not seen the mod operation before, let me explain; it means the remainder after dividing by the number that follows it. For example, b = a + 1 mod 4 means b is the remainder of a + 1 divided by 4. So, if a is 12, then b will be 1, because a + 1 is 13, and 13 divided by 4 gives a remainder of 1.
Copy the following code into a file named random.s.
.globl Random
Random:
xnm .req r0
a .req r1
mov a,#0xef00
mul a,xnm
mul a,xnm
add a,xnm
.unreq xnm
add r0,a,#73
.unreq a
mov pc,lr
This is an implementation of the random function, using a value finally generated in register r0 as input, while the next number is the output. In my case, I use a = EF0016, b = 1, c = 73. This choice is arbitrary but needs to meet the above restrictions. You can use any numbers to replace them, as long as they comply with the aforementioned rules.
4. Pi-casso
OK, now we have all the functions we need, let’s try them out. After obtaining the address of the frame buffer information, modify main as follows:
r0 containing the frame buffer information address to call SetGraphicsAddress.random to generate the next x coordinate, using the last random number as input.random again to generate the next y coordinate, using the generated x coordinate as input.colour value to call SetForeColour, then increment the colour value. If it exceeds FFFF~16~, ensure it returns to 0.As always, you can find this solution on the download page.
After you finish, test it on the Raspberry Pi. You should see a series of color-incrementing random lines appearing on the screen at a very fast rate. It continues indefinitely. If your code doesn’t work correctly, please check our troubleshooting page.
If everything goes well, congratulations! We have now learned meaningful graphics and random numbers. I encourage you to use it to draw lines because it can be used to render anything you want, and you can explore more complex patterns. Most of them can be generated by lines, but that requires better strategies? If you are willing to write a line drawing program, try using the SetPixel function. What happens if instead of setting the pixel value, you increment it a bit? What kind of patterns can you generate with it? In the next lesson Course 8: Screen 03[2], we will learn the valuable skill of drawing text.
via: https://www.cl.cam.ac.uk/projects/raspberrypi/tutorials/os/screen02.html
Author: Alex Chadwick[4] Topic: lujun9972 Translator: qhwdw Proofreader: wxy
This article is originally compiled by LCTT and proudly presented by Linux China
