Directed Acyclic Graphs

Def Directed graph with no cycles are called directed acyclic graphs.

Lemma 1: every DAG has at least one source (proof by contradiction)

Lemma 2: If v is a souce vertex of G, then G is a DAG if and only if G-v is a DAG

Find topological ordering

While G has at least one vertex
If G has some source,
Choose one source and output it
Delete the source and all its outgoing edges from G
Else
Return that G is not a DAG

Compile By Hand

Basic arithmetic

g = h + A[8]; 
// r0 stores A array; r1 stores h; r2 to store g.

ADD r0, r0, #32
LDR r3, [r0]
@ r0 = &A + 8 * 4, since int is of 4 bytes.

LDR r3, [r0, #32]

Accessing arrays

void foo (int *p, int size){
    // p stored in r2, size stored in r1
    *p = 0; 
    *(p + 1) = 0;
    *(p + size - 1) = 0;
}

foo:
MOV r2, #0; @ store 0 in *p
STR r2, [r0] @ *p = 0
MOV r3, #4
ADD r4, r0, r3 @ p + 1 in C
STR r2, [r4] @ store 0 in *(p + 1)
SUB r1, r1, #1 @ r1  = size - 1
MUL r4, r1, r3 @ r4 = r1 * r3
STR r2, [r0, r4] @ store 0 in *(p + size - 1)

Data transfer instructions

void swap (int *x, int *y){
    // x stored in r0, y stored in r1
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

swap:
LDR r2, [r0] 
@ Load *x from memory and store in r2
LDR r3, [r1]
@ Load *y from memory and store in r3
STR r3, [r0]
@ Store r3 in register to *x in memory
MOV r2, [r1]
@ Store r2 (tmp) in register to *y in memory

• For short, LDR -> LDRSH, STR -> STRSH
• For unsigned short, LDR -> LDRH, STR -> STRH

Linked lists

• head -> *next -> *next -> … -> value

head -> value = 100;
head -> *next -> value = 100; 
// r0 stores the first value

MOV r1, #100
STR r1, [r0] @ store to memory
...
LDR r3, [r0, #4] @ store 100 to next value
STR r1, [r3]

ARM Instruction

ARM goto Instruction

goto label (C) is the same as B label in ARM.

Conditional Branch

1. Set the condition bits (N, Z, V, C) in the program status register.
2. Then check on these condition bits to branch conditionally.

Conditional bits

N = 1 if result is Negative

Z = 1 if result is Zero

V = 1 if there’s overflow

C = 1 if there’s carry out

SUBS (with the ending S) sets conditional bits in cpsr register.

SUBS r1, r0, #0

r0 = r1 – #0, and set the condition bits NZVC based on the result.
If r1==r2, then N = 0, Z= 1, V = 0, C =1
If r < r2 (no overflow), then N =1, Z = 0, V=0

Another way to do that is to use a ‘Comparison Instruction’

CMP r1, r2
BEQ label  @if Z = 1, then go to label

• Compare and set condition bits
• Subtract a register or an immediate value from a register value and updates status register
• Then check on these condition bits to branch conditionally

COM r0, #4
BEQ this_instr
ADD r4, r5, r6
B end
this_instr: SUB r0, r0, #1
end:

if(r0 == 4)
    r0 --;
r4 = r5 + r6;

if(r0 != 4)
    r4 = r5 + r6;
r0 --;

ARM Decision Instructions

[table id=3 /]

The condition is T/F based upon the fields in the Program Status Register.

If…else

if (x==y)
    x += y;
else
    x -= y;

CMP r01, r1
BNE else_aprt
ADD r0, r0, r1
B end
else_part: SUB r0, r0,r1
end:

ARM Memory Map / Basic Instructions

 ARM Memory Map

[table id=2 /]

• “Text” (instructions in machine language)
• “Data” contains any global or static variables which have a pre-defined value and can be modified. That is any variables that are not defined within a function (and thus can be accessed from anywhere) or are defined in a function but are defined as static so they retain their value across subsequent calls.
• “BSS” also known as uninitialized data, is usually adjacent to the data segment. The BSS segment contains all global variables and static variables that are initialized to zero or do not have explicit initialization in source code.
• “Heap” (for dynamically allocated data)
• “Stack” (for function local variables)
• Heap and stack change in size as the program executes.

View the memory map using “size”

$ gcc -O foo.c -c
$ size foo.o
   text    data     bss     dec     hex filename
     52       0       0      52      34 foo.o

Program Execution

Interactions between CPU, registers, and memory. Each instruction (4 bytes) handles the data from registers (more frequently) and memory.

Registers

Each ARM register is 32 bits wide. There are 30 general purpose registers (6 status registers, 1 program counter).

r0 to r12, general
r13, stack pointer,
r14, subroutine Link Register
r15, program counter

Basic Type of Instructions

• Arithmetic (involves only CPU and registers)

Compute the sum (or difference) of two registers, and store the value in a register.

Move the contents of one register to another

• Memory Instructions (transfer data between memory and registers)

• Control Transfer Instructions: Change flow of execution

In C:
a = b + 10;

In ARM:
ADD r0, r1, #10

#10 is an immediate (constant), which has fixed length of 4 bytes.

Assignment Instructions

In C:
a = b; // a and b are integers
a = 10;

In ARM:
mov r0, r1 @r0 = r1

Data Transfer

Separate instructions to transfer data between registers and memory:

• Memory to register (LOAD)
• Register to memory (STORE)

Load/store Syntax

LDR r0, [r1]

• r1 must be a register that contains a valid memory location (as a pointer).
• Copy 4 bytes from the location pointed by r1 into r0
• Equivalent to r0 = * r1; (in C)

STR r0, [r1]

• r1 stores the address of destination memory.
• Store contents of r0 to location pointed by r1.
• *r1 = r0; (in C)

In Little Endian machines (ARM and Intel x86), the least significant byte (like 5 in 0x00000005) goes into the lowest memory address (like 0x200 of 0x200 to 0x0203).

Variations on LDR/STR

LOAD

LDRH r0, [r1] @ r1 points to 2 bytes (unsigned)

• Fill the significant bits with zeros.
• Treat content pointed by r1 as unsigned.

LDRSH r0, [r1] @ r1 points to 2 bytes (signed)

• Treat content pointed by r1 as signed.
• Identify if the most significant bit is 0 or 1 (positive or negative) and do sign expansion.
• Fill F’s in the spare bits.

LDRB r0, [r1] @ r1 points to 1 byte (unsigned)

LDRSB r0, [r1] @ r1 points to 1 byte (signed)

STORE

STR r0, [r1] @ store 4 bytes
STRH r0, [r1] @ store least significant 2 bytes
STRB r0, [r1] @ store least significant byte

There’s no STRSH or STRSB, since the two bytes or one byte can be signed or unsigned. Raw data in r0 ought not be changed.

Struct

A struct is a data structure composed of simpler data types.

There is no methods or inheritance.

struct point {
    int x;
    int y;
}

main(){
    struct point p1;
    // get memory allocated for two int
    p1.x = 5;
    p2.y = 10;
}

void printPoint(struct point p){
    printf("(%d,%d)", p.x, p.y);
}

struct point *p;
p = malloc(sizeof(struct point));
printf("x is %d\n",(*p).x);
printf("x is %d\n", p->x);

Dangling Pointers & Memory Leaks

Dangling pointer

Pointer points to a memory location that no longer exists.

Memory Leaks

Memory allocated by a program is not freed.

The program is particularly acute if memory allocated in heap can no longer be accessed.

void foo(){
    int * p = malloc(8);
    p = NULL;
    /* memory previously pointed by p can never
     * be freed. */
}

int * f2(int null){
    int mem2[num];
    return mem2;
} 
// DANGLING POINTER
// never return the address of a local variable.

Dynamic Memory Allocation

malloc

void * malloc (size_t s) 
//size_t defined in stdlib.h

• Allocate a block of ‘s’ on the heap and return the starting address of that block, return a void pointer
• Return NULL if memory can’t be allocated.

int * arr = malloc(5 * sizeof(int));
//allocate memory for an int array of size 5

calloc

calloc() works like malloc, but initializes the memory to zero if possible. The prototype is:

void *calloc(size_t num, size_t size);
// equivalent to malloc()
void *malloc(size_t num * size)

Num is the number of elements, and size the byte size of each element.

realloc

void* realloc (void * p, size_t s);

Extend or shrink the block pointed by p to s bytes

Safe instructions to use realloc

int *tmp;
if ((tmp = realloc(ip, sizeof(int) * (INITIAL_ARRAY_SIZE + 5))) == NULL) {
    fprintf(stderr, "ERROR: realloc failed");
}
ip = tmp;

If realloc fails to extend memory pointed by ptr, ptr will point to NULL, and its previous allocated memory will never be accessed (memory leak).

bzero

bzero(3) fills the first n bytes of the pointer to zero. Prototype:

void bzero(void *s, size_t n);

memset

To set the value to some other value (or just as a general alternative to bzero).

void *memset(void *s, int c, size_t n);

Specify c as the value to fill for n bytes of pointer s.

free

void free(void * ptr)

Free the heap block pointed by p

int *p = malloc(8);
// allocated 8 bytes to p
free(p);
free(p); //program crashes [runtime error]

After freeing a pointer, should point it to NULL.

Protected: Download Mirror

A Cultural Project

Here I made a cultural project about 1992 Los Angeles riots.

Capstone Project

Purpose

This project was designed to recall the history in the perspectives from different ethnic groups, with a mainstream media timeline for comparison. The map can you walk you through the event in a flat LA space layout.

To see LA Times timeline for comparison:  Click here

Map Comparison

Map of Los Angeles by Average Household Income

Racial Dot Map In LA Highlights Segregation By Neighborhood

The two maps above indicating racial and economic dispersion of LA can be compared with the map provided by this site. The violence of the riots in 1992 happened most in areas of the non-white, low-income households.

References

Images:

• AP Images:  Click here
• LA Times: LA Times Timeline  Photos
• Other websites: stolinsky.com

Videos:

• YouTube (links embedded in player)
• LA Times: LA Times Timeline

Maps:

The maps uses Google Maps data with customized markers. Coordinates are parsed manually.

Texts:

Most texts are hand-written. There are textual explanations from the following sources:

• AP Images:  Click here
• LA Times: LA Times Timeline
• Wikipedia: Click here
• Anna Smith’s Twilight Los Angeles, 1992

You Have An Accent!

Yes, I have an accent. Everybody has. If you are told you have an accent, that means they way what you speak is different to most people in this area do.

In a university, talking to people from everywhere, I find it easy to identify an accent and thus have an idea of where he or she comes from. Nevertheless, most people don’t, because they are not careful enough. If you can distinguish Indian English or Japanese English, it is not hard to tell the difference among America’s mid-west, California, and the Eastern coast. It is also not a problem to pinpoint which part of UK a person comes from, Scotland, Yorkshire, London, or London’s east-end. The fact is, listen. 

Accents shift frequently. I can speak many English accents in different contexts. The variation is not exclusive to English. People in China typically have two accents, the standard Mandarin and their own dialect.

Language and its accents are intersting objects as they carry information about the speakers’ whereabouts and enrich an distinct local culture. As people migrate, accents are also an intangible mark they take with them.