ICS 51: Introductory Computer Organization Lab#3 (lab3.zip)
In this lab, you will learn how to use x86 assembly instructions to:
1. implement FOR and WHILE loop constructs
2. read/write from/to memory
1. Implementing loop constructs in x86 assembly:
1.1. WHILE loop:
The most general loop is WHILE loop which takes the following form in C/C++:
while (condition)
{
>
}
TherearetwoimportantpointstonoteaboutaWHILEloop.First,thetestforterminationappearsat
thebeginningoftheloop.Second,asadirectconsequenceofthepositionoftheterminationtest,the
body of the loop may never execute.
A WHILE loop can be converted to x86 assembly using the following pseudo-code template:
BeginningOfWhile:
if(condition)
{
>
jmp BeginningOfWhile
}
EndOfWhile:
Therefore,youcanusethetechniquefromearlierlabtoconvertIFstatementstoassemblylanguage
alongwithasingleJMPinstructiontoproduceaWHILEloop.Anexampleofsuchtranslationis
shown below:
C code x86 Assembly code
while ( c > 0 )
{
a = b + 1;
c--;
}
mov eax, a
mov ebx, b
mov ecx, c
BeginningOfWhile:
cmp ecx, 0
jle EndOfWhile
mov eax, ebx
inc eax
dec ecx
jmp BeginningOfWhile
EndOfWhile:
mov a, eax
mov c, ecx
1.2. FOR loop:
AFORloopisessentiallyaWHILELoopwithaninitialstate,acondition,andaniterativeinstruction.
For instance, the following generic FOR Loop in C/C++:
for(counter initialization; condition; counter increment/decrement)
{
>
}
can be converted to the following pseudo-code using WHILE loop:
counter initialization
while(condition)
{
>
counter increment/decrement
}
WealreadyknowhowtotranslateaWHILElooptox86assembly,thereforewecantranslateany
FOR loop using the above template.
2. x86 Memory Addressing Modes:
Thememoryaddressingmodedetermines,foraninstructionthataccessesamemorylocation,how
the address for the memory location is specified.
To summarize, the following diagram shows the possible ways an address could be specified:
Eachsquarebracketintheabovediagramindicatesanoptionalpartoftheaddressspecification.
Theseparts(fromlefttoright)are:Aregisterusedasabaseaddress,aregisterusedasanindex,a
width(orscale)valuetomultiplytheregisterby,andandisplacement(akaoffset)whichisaninteger.
Theaddressiscomputedasthesumof:thebaseregister,theindextimesthewidth,andthe
displacement. Here are couple of common modes with examples:
Mode Example
Direct (or Absolute)
Register indirect
Register indirect with offset
Scaled-index with offset
Base with scaled-index
mov eax, [1000]
mov eax, [ebx]
mov eax, [ebp-8]
mov eax, [esi*4 + 100]
mov eax, [edx + esi*4]
Notethat,whenaccessingmemory,theoperandwillalwaysbe surroundedby square
brackets("["and"]").Thesquarebracketsmeanthattheoperandpointstoamemorylocation
and that data should be read from or written to that memory location.
So in general, MOV ABC, [XYZ] means: “copy anything that XYZ points to and put it in ABC”.
2.1. Scalar variables
2.1.1 Variables passed by pointer
Weuse“registerindirect”addressingmodewhentheaddressofavariableispassedtothefunction
asapointerargument.Inthefollowingexample,“num”isapointertoanintegerwewouldliketo
increment its value.
C x86 Assembly
void increment (int *num) {
(*num)++;
}
void increment (int *num) {
__asm{ mov eax, num
add dword ptr [eax], 1 }
}
2.1.2. Local variables or function arguments
Wealreadyknewhowtodealwiththiscasewithoutevenknowinganythingaboutaddressingmodes.
ThatisbecauseVisualStudio,forconvenience,allowsyoutousethevariable’snameinorderto
read the value of a local variable or update it with a new value.
C x86 Assembly
int increment (int num) {
num++;
return num;
}
int increment (int num) {
__asm{ add num, 1
}
return num; }
However,wewilllearninlab#3thatinfact“registerindirectwithoffset”modeisusedbyVisual
Studio for accessing values on the stack (both local variables and function arguments).
2.2. Array operands
2.2.1. Arrays passed by a pointer
Weuse“basewithscaled-index”mode.Inthismodeyouspecifyabase,anindexregister,anda
scalefactor.Scalefactorischosentobeequaltoelementsizeinbytesandtheoptionsare1,2,4,or
4
8.Intheexamplebelow,sincearrayisoftypeintegerandeachintegeris4bytes,weuse“4”toscale
the index (esi = element_index).
C x86 Assembly
void set_to_zero (int *arr, int element_index)
{
arr [element_index] = 0;
}
void set_to_zero (int *arr, int element_index)
{ __asm{
mov esi, element_index mov edx, arr
mov dword ptr [edx + esi*4], 0 }
}
3. Size directives when accessing memory:
Ingeneral,theintendedsizeoftheofthedataitematagivenmemoryaddresscanbeinferredfrom
theassemblyinstructioninwhichitisreferenced.Forexample,ifweareloadinga32-bitregister,the
assembler could infer that the region of memory we were referring to was 4 bytes wide. For example:
mov eax, [ebp-8]
However,in somecasesthesizeof a referred-tomemoryregionisambiguous.Considerthe
instruction:
mov [ebx], 2
Shouldthisinstructionmovethevalue2intothesinglebyteataddressEBX?Perhapsitshouldmove
the32-bitintegerrepresentationof2intothe4-bytesstartingataddressEBX.Sinceeitherisavalid
possibleinterpretation,theassemblermustbeexplicitlydirectedastowhichiscorrect.Thesize
directivesBYTEPTR,WORDPTR,DWORDPTR,andQWORDPTRservethispurpose,indicating
sizes of 1, 2, 4, and 8 bytes respectively.
For example:
mov byte ptr [ebx], 2 ; Move2intothesinglebyte(8-bitrepresentation)atthe
address stored in EBX.
mov word ptr [ebx], 2 ; Movethe16-bitintegerrepresentationof2intothe2
bytes starting at the address in EBX.
mov dword ptr [ebx], 2 ; Movethe32-bitintegerrepresentationof2intothe4
bytes starting at the address in EBX.
Example: Finding the maximum element in an array of integers (find_max.c)
4. Your task:
Inthislabassignment,youwillimplementthekerneloftwoimagemanipulationtechniques:Image
Thresholding and Image Rotation.
TherearevariousimageformatssuchasJPEG,PNGorGIF.Themajordifferencebetweenthese
formats is the compression technique each one uses to reduce the size of an image.
Inthisassignment,wehaveprovidedyouwiththecodetocompress/decompressPNGfiles.Theonly
part you will have to implement in assembly is the desired image manipulation kernel (red box).
Part 1) Image Thresholding:
Image thresholdingisasimple,yeteffective,wayofpartitioninganimageintoaforegroundand
background.Thisimageanalysistechniqueisatypeofimagesegmentationthatisolatesobjectsby
converting grayscale images into binary images. An example of such conversion is shown below:
lena.png lena_binary.png
Yourtaskistowritethebodyofthethresholdingfunctionthattakesinanarrayofpixelsofa
grayscaleimagealongwithits dimensionsanda thresholdvalueandappliesbinaryimage
thresholdingontheinputimage.Theinputimageforthispartisasquaresizedgrayscaleimage.For
grayscaleimages,onebyteisusedtostoreeachpixel’sintensitywherethepossiblevaluesrange
from0x00to0xFF.Inotherwords,theimageisstoredina2Darraywhereeachelementisabyte.
Refer to the handout on memory layout to learn how a 2D array is stored in 1D memory.
Thisfunctionshouldreplacethevalueofeachpixelinthegrayscaleimagewiththemaximum
possiblevalue(0xFF,i.e.brightestvalue),iftheintensity(value)ofthatpixelisgreaterthanorequal
to the given threshold, or otherwise with the minimum value (0x00, i.e. darkest value).
Part 2) Image Rotation:
Inthesecondpartofthislab,youareimplementingafunctiontorotateagivencolorimage90
degrees clockwise.
authoritah.png authoritah_rotated_clockwise.png
Theinputimageisasquaresizedcolorimagewhereitspixelsarestoredina2Darraybutunlikepart
1,hereeachpixeltakes4bytesinmemory.Duringrotation,youcannotuseanyadditionalarrayfor 1
temporary storage and the rotation should be done in place.
1 In RGBA color space, three bytes are used to represent the color by setting by using one byte for each Red, Green and
Blue channels and the fourth byte is used to represent the image opacity.
8
Togetanideaofhowtoimplementtherotationkernel,lookattheabovefigureandobservewhat
happenstoasamplepixel(p0)aftera90degreesclockwiserotation.Aftertherotation,p0should
replacep90.p90ontheotherhandshouldreplacep180.Similarlyp180willreplacep270andfinally
p270 replaces the original p0.
Asyouprobablynoticed,duringeachiterationwearerotatingfourpixelssimultaneously.Therefore,
weonlyneedtoiterateoveraquarteroftheimagetorotatetheentireimage.Intheabovefigure,itis
enough to iterate over the pixels in the red triangle in order to rotate the entire image.
Ineachiteration,youshouldpickadifferentp0intheredtriangleandthenfindthecorresponding
pixelsintheotherthreetrianglesandfinallyrotationallyexchangetheirvalues.Asanotherexample
take a look at, q0, q90, q180 and q270.
Wehavedefinedfourvariablesintheimagerotationfunction,calleda0,a90,a180,a270,thatyou
mayusetostoretheaddressofthefourpixels.Havingallfouraddresses,youwillbeabletoreadthe
pixels and rotate their values: (p0->p90->p180->p270->p0)
Youmayusethesefourvariablesforanyotherpurposeyouwant.Butyoucannotdefinenew
variables in the code.
Thetemplatecode(lab3.cpp)andthetester(lab3-tester.cpp)alongwithPNGcompress/decompress
library(lodepng.cppandlodepng.h)andtestimagesaregiventoyou.Downloadthemfromhere.You
needtomakeanewprojectandimportthesefourfilesintoit.However,rememberthatyouareonly 2
allowedtomakechangesinthemarkedblocksoflab3.cpp.Theexpectedoutputscanbeseenhere
for comparison.
● Submit ONLY your completed lab3.cpp.
● Do NOT zip it.
● Do NOT submit your project/solution/output files.
2 “lodepng.h” has to be added as a header file to your project. All other *.cpp files are source files.