diff options
| -rw-r--r-- | Makefile | 8 | ||||
| -rw-r--r-- | index.md | 3 | ||||
| -rw-r--r-- | index.sh | 12 | ||||
| -rw-r--r-- | sem1-projekt/mifare.md | 58 | ||||
| -rw-r--r-- | sem1/BfCI/husk.txt | 14 | ||||
| -rw-r--r-- | sem1/BfCI/mm1.md | 177 | ||||
| -rw-r--r-- | sem1/BfCI/mm3.md | 19 | ||||
| -rw-r--r-- | sem1/algo/.gitignore | 2 | ||||
| -rw-r--r-- | sem1/algo/lek1/merge.c | 115 | ||||
| -rw-r--r-- | sem1/algo/mm2/linked/Makefile | 31 | ||||
| -rw-r--r-- | sem1/algo/mm2/linked/Readme.md | 22 | ||||
| -rw-r--r-- | sem1/algo/mm2/linked/llist.c | 89 | ||||
| -rw-r--r-- | sem1/algo/mm2/linked/llist.h | 22 | ||||
| -rw-r--r-- | sem1/algo/mm2/linked/main.c | 45 | ||||
| -rw-r--r-- | sem1/algo/mm2/linked/node.c | 57 | ||||
| -rw-r--r-- | sem1/algo/mm2/linked/node.h | 23 | ||||
| -rw-r--r-- | sem1/algo/mm2/queue.c | 100 | ||||
| -rw-r--r-- | sem1/algo/mm3/multiply.c | 56 | ||||
| -rw-r--r-- | sem1/algo/mm3/opgaver.md | 49 | ||||
| -rw-r--r-- | sem1/module.c | 12 | ||||
| -rw-r--r-- | sem1/osc/mm1/.gitignore | 10 | ||||
| -rw-r--r-- | sem1/osc/mm1/mm1/Makefile | 7 | ||||
| -rw-r--r-- | sem1/osc/mm1/mm1/Readme.md | 34 | ||||
| -rw-r--r-- | sem1/osc/mm1/mm1/jmod.c | 70 | ||||
| -rw-r--r-- | sem1/osc/mm1/mm2/tprog.c | 71 | ||||
| -rw-r--r-- | sem1/osc/mm3/opgaver.md | 47 |
26 files changed, 1148 insertions, 5 deletions
@@ -1,14 +1,18 @@ -MD_FILES = $(wildcard *.md) $(wildcard */*.md) +MD_FILES = $(shell find . -type f -name '*.md') HTML_FILES = $(patsubst %.md, %.html, $(MD_FILES)) +index.html: $(HTML_FILES) index.sh + sh index.sh $(HTML_FILES) | pandoc --output $@ %.html: %.md pandoc $^ --output $@ + .PHONY: all clean -all: $(HTML_FILES) +all: $(HTML_FILES) index.html clean: rm -rf $(HTML_FILES) + rm index.html diff --git a/index.md b/index.md deleted file mode 100644 index 5354437..0000000 --- a/index.md +++ /dev/null @@ -1,3 +0,0 @@ -# Julian noter - -1. [test](test/test.html) diff --git a/index.sh b/index.sh new file mode 100644 index 0000000..8650d4e --- /dev/null +++ b/index.sh @@ -0,0 +1,12 @@ +# Generate index.md file + +echo '# Julian Noter' +echo + +# Make toc +HTML_FILES=$@ + +for url in $HTML_FILES; do + echo "- [$url]($url)" +done + diff --git a/sem1-projekt/mifare.md b/sem1-projekt/mifare.md new file mode 100644 index 0000000..448292d --- /dev/null +++ b/sem1-projekt/mifare.md @@ -0,0 +1,58 @@ +# Vulnabilites + +Using the unsecure propreitary crypto1. +Companies often do this however custom crypto often ends wrong. + +Ting der gør crypto1 usikker. + +- Kun 48 bits. Dette er et problem da crypto1 er fuldt reversed. +- Random generator til 32 bit nounce er kun 16 bit entropy. + + Dette betyder at nouncene vil gentage sig rimelig hurtigt, og eftersom den starter i known state kan man time sig til en nounce man kender. + + Dette er heldigvis fixet i senere versioner hvor man har lavet en bedre random generator. +- Nested attack hvor man ud med en ud fra en sector key kan udlede 32 bit fra keystreamen. + + Her authentikator man til en sector, og laver derefter en nestet authentification. + I denne nestet bliver sendt krypteret, men fordi man kan regne ud hvad den er kan man udlede keystream(du ved fordi xor). + +- Parity bits deler en keystream bit med den næste bit. Dette betyder at den kan udledes. + + Denne fejl kan ikke fixes let ligesom den med nouncene. + +- Keystream fra fejl + + Hvis man sender et forkert svar ved challenge-response, sender den en fejl **kryperet**. + + Eftersom man kender fejlkoden kan man få 4 bits fra keystream. + + Denne fejl kan heldigvis fixes da læsere alligevel ikke bruger denne fejlbesked(de kan jo ikke læse den når den er krypteret). + +- LFSR rollback + + Hvis man kan udlede LFSR på et eller andet tidspunkt kan man regne ud hvad den var fra i starten, hvis man har det data der er puttet ind. + + Eftersom den starter med at være secret key kan man derfor udelede den. + +- Ulige bit filter + + Noget med at filtret der feeder tilbage til LFSR kun bruger de ulige bits. + + Dette betyder at man kan lettere kan komme tilbage til starten af LFSR. + Forstår ikke helt hvordan. + +## Angreb for key + +De starter med at hente en masse nounces ind med nestet attack. + +Ret avanceret. +Noget med propability. +De skriver noget med en sum function jeg ikke helt forstår. +(edit kan se det står længere nede. Ved ikke helt om jeg læser det, der er ret meget. Vi ved der der). + +De får nogle forskellige keys det måske kan være. + +De kan tage og prøve at dekode alle nouncene med en key for at test den. +De ved at key'en er god når parity passer. + +Hvis parity ikke passer er der 1/2 change for at keyen er god. diff --git a/sem1/BfCI/husk.txt b/sem1/BfCI/husk.txt new file mode 100644 index 0000000..e5a7b96 --- /dev/null +++ b/sem1/BfCI/husk.txt @@ -0,0 +1,14 @@ + + +log(log(x^4)) = log(log(x)) + +Husk at 4 flytter sig uden for log(x). + + +x^2-1 = (x-1)(x+1) + +lim(to inf) f(x) over g(x) = { + 0 -> f is O(g) + const -> f(x) = THETA(g(x)) + INF -> f is OMEGA(g) +} diff --git a/sem1/BfCI/mm1.md b/sem1/BfCI/mm1.md new file mode 100644 index 0000000..933086c --- /dev/null +++ b/sem1/BfCI/mm1.md @@ -0,0 +1,177 @@ +# Logic + +TODO Manger at lave en summary. + +## Opgaver + +### 1. + +A) Yes, T +B) Yes, T +C) Yes, T +D) Yes, T +E) No +F) No + +### UNKNOWN ORIGIN (12.) + +A) if you have the flu, you miss the final examination +B) you pass the course if and only if you do not miss the final examination +C) if you miss the final examination, you do not pass the course +D) you have the flu, miss the final examination and pass the couse + +### 15. (13.) + +A) ¬p +B) p ^ ¬q +C) p -> q +D) ¬p -> ¬q +E) p -> q +F) q ^ ¬p +G) q -> p + +### 20. (18.) + +A) T +B) T +C) F +D) T + +### UNKNOWN ORIGIN(31.) + +A) + +| p | ¬p | p ^ ¬p | +| -- | -- | -- | +| T | F | F | +| F | T | F | + +B) + +| p | ¬p | p v ¬p | +| -- | -- | -- | +| T | F | T | +| F | T | T | + +C) + +| p | q | p v ¬q | ( p v ¬q) -> q | +| -- | -- | -- | -- | +| T | T | T | T | +| T | F | T | F | +| F | T | F | T | +| F | F | T | F | + +D) + +| p | q | ( p v q) -> ( p ^ q ) | +| -- | -- | -- | +| T | T | T -> T = T | +| T | F | T -> F = F | +| F | T | T -> F = F | +| F | F | F -> F = T | + +E) + +| p | q | (p -> q) | (¬q -> ¬p) | (p -> q) <-> (¬q -> ¬p ) | +| -- | -- | -- | -- | -- | +| T | T | T | T | T | +| T | F | F | F | T | +| F | T | T | T | T | +| F | F | T | T | T | + +F) + +| p | q | (p -> q) | ( q -> p ) | (p -> q) -> ( q -> p) | +| -- | -- | -- | -- | -- | +| T | T | T | T | T | +| T | F | F | T | T | +| F | T | T | F | F | +| F | F | T | T | T | + + +### (40. ) + +All the paranterees must be true, they can be split up. + +r is in two parantesees ( q v ¬r ) and ( r v ¬p ). + +If r is true q must also be true for ( q v ¬p ). + +Therefore in ( p v ¬p ) p must also be true. + +Therefore it creates a kind of circle, that also works then one is false. + +### (44. ) + +A) + + 01011 + 11011 +v----- + 11011 + 11000 +^----- + 11000 + +B) + + 01111 + 10101 +^----- + 00101 + 01000 +v----- + 01101 + +C) + + 01010 + 11011 +x----- + 10001 + 01000 +x----- + 11001 + +D) + + 11011 + 01010 +v----- + 11011 + + 10001 + 11011 +v----- + 11011 + + 11011 + 11011 +^----- + 11011 + + +### (7. ) + +Already done this + +### (9. ) + +The rest is just stupid. + +### (20. ) + +| p | q | p x q | p <-> q | +| -- | -- | -- | -- | +| T | T | F | T | +| T | F | T | F | +| F | T | T | F | +| F | F | F | T | + +The two last columns are the negatives of each other thus + +p x q = p <-> q + + + diff --git a/sem1/BfCI/mm3.md b/sem1/BfCI/mm3.md new file mode 100644 index 0000000..a0bb1b8 --- /dev/null +++ b/sem1/BfCI/mm3.md @@ -0,0 +1,19 @@ +# Lektier + +## Steps til strong induction bevis + +1. *[Basis step]* start med at bevis at P(1) er sandt. Altså hvad resten vil bygge på. +2. *[Inductive step]* bevis at hvis de første P(1 til k) er sandt er P(k+1) også sandt. + +## Recursive function + +En funktion der regner factorial. +Altså f(x) = 1 * 2 * 3 * .. * x + +Her vil f(1) = 1. +Og resten vil være f(x) = x * f(x-1). + +f(1) = 1 +f(2) = 2 * f(1) = 2 * 1 = 2 +f(3) = 3 * f(2) = 3 * 2 = 6 +f(4) = 4 * f(3) = 4 * 6 = 16 diff --git a/sem1/algo/.gitignore b/sem1/algo/.gitignore new file mode 100644 index 0000000..38aee6d --- /dev/null +++ b/sem1/algo/.gitignore @@ -0,0 +1,2 @@ +**/a.out +**/build diff --git a/sem1/algo/lek1/merge.c b/sem1/algo/lek1/merge.c new file mode 100644 index 0000000..997bcb8 --- /dev/null +++ b/sem1/algo/lek1/merge.c @@ -0,0 +1,115 @@ +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> +#include <stdint.h> + +#define DO_PRINT 0 + +void printArr(int *arr, size_t len) { + printf("{"); + for(int i = 0; i < len; i++) { + printf(" %d%s", arr[i], i+1 == len ? " " : ","); + } + printf("}\n"); +} + +int *genArr(size_t len, int div) { + /* Make array */ + int *arr = (int *) malloc(len * sizeof(int)); + + if( arr == NULL) { + return NULL; + } + + /* Fill it with random */ + while( len-- ) { + arr[len] = div - (rand() % (div*2)); + } + + return arr; + +} + +int mergeSort(int *arr, size_t len) { + /* Check if len is one(then it's sorted */ + if (len <= 1) { + return 0; + } + /* Calculate array sizes */ + size_t q = len/2; + size_t rl = len-q; + + /* Make arrays */ + int *left = (int *) malloc(q * sizeof(int)); + if( left == NULL ) { + return 1; + } + int *right = (int *) malloc(rl * sizeof(int)); + if( right == NULL ) { + return 1; + } + + /* Copy data */ + memcpy(left, arr, q * sizeof(int)); + memcpy(right, arr + q, rl * sizeof(int)); + + /* Sort each */ + mergeSort(left, q); + mergeSort(right, rl); + + /* Merge them into arr */ + for(int i=0, j=0, k = 0; k < len; k++) { + if( i < q && ( j == rl || left[i] <= right[j] ) ) { + arr[k] = left[ i++ ]; + } else { + arr[k] = right[ j++ ]; + } + } + + /* Free the pointers */ + free(left); + free(right); + + return 0; +} + +void test(size_t len) { + + int *a = genArr(len, len); + +#if DO_PRINT == 1 + printArr(a, len); + printf("\n\n"); +#endif + + clock_t begin = clock(); + mergeSort(a, len); + clock_t end = clock(); + +#if DO_PRINT == 1 + printArr(a, len); +#endif + + clock_t diff = end - begin; + printf("Sorting %d long array took %d : %f s\n", len, diff, (double)diff/CLOCKS_PER_SEC); + + free(a); +} + +void bench() { + + size_t len = SIZE_MAX; + + srand((unsigned) time(NULL)); + for (int i = 1; i < len; i *= 2) { + test(i); + } +} + +int main(void) { + + bench(); + + return 0; +} diff --git a/sem1/algo/mm2/linked/Makefile b/sem1/algo/mm2/linked/Makefile new file mode 100644 index 0000000..881143c --- /dev/null +++ b/sem1/algo/mm2/linked/Makefile @@ -0,0 +1,31 @@ +CC = gcc +# Enable gdb and pull include files from current dir +CFLAGS = -ggdb -I. +LDFLAGS = + +BINARY = linked +BUILD_DIR = build + +# Capture c files +c_files = $(wildcard *.c) + +# Convert c names to corrosponding o names +OBJ = $(patsubst %.c, $(BUILD_DIR)/%.o, $(c_files)) + +# $@ is the %.o file and $^ is the %.c file +$(BUILD_DIR)/%.o: %.c + mkdir -p $(dir $@) + $(CC) -c -o $@ $^ $(CFLAGS) + +# $@ becomes left part thus linked +$(BINARY): $(OBJ) + $(CC) -o $@ $^ $(LDFLAGS) + +.PHONY: clean run + +run: $(BINARY) + ./$(BINARY) + +clean: + rm -f $(OBJ) $(BINARY) + rmdir $(BUILD_DIR) diff --git a/sem1/algo/mm2/linked/Readme.md b/sem1/algo/mm2/linked/Readme.md new file mode 100644 index 0000000..679dcf3 --- /dev/null +++ b/sem1/algo/mm2/linked/Readme.md @@ -0,0 +1,22 @@ +# Linked list assignment + +The linked list stuff is in node.c and higher level list functions in llist.c. + +Build with make: + +``` +make +``` + +To build and run + +``` +make run +``` + +To clean up when we are done. + +``` +make clean +``` + diff --git a/sem1/algo/mm2/linked/llist.c b/sem1/algo/mm2/linked/llist.c new file mode 100644 index 0000000..41ab892 --- /dev/null +++ b/sem1/algo/mm2/linked/llist.c @@ -0,0 +1,89 @@ +#include "llist.h" + +#include <string.h> +#include <stdio.h> + + +#define OUT_OFF_BOUNDS 2 + +void llist_init(llist_t *list) { + /* Zero out structure */ + list->head = list->root = NULL; + + list->len = 0; + +} + +void llist_append(llist_t *list, int val) { + /* Insert node after HEAD */ + list->head = node_insert(list->head, val); + + /* Check if was list is empty */ + if( list->len == 0 ) { + /* Set root */ + list->root = list->head; + } + + /* Increase count */ + list->len++; +} + +node_t *llist_get_node(llist_t *list, unsigned int index) { + /* Check if we have it */ + if( index >= list->len ) { + return NULL; + } + + /* Find the best way to go down the list */ + int direc = index > (list->len / 2) ? -1 : 1; + + /* Setup start location */ + int pos = direc > 0 ? 0 : list->len-1; + node_t *node = direc > 0 ? list->root : list->head; + + /* Go to index */ + while( pos != index ) { + /* TODO kinda risky, we trust our math and len */ + node = direc > 0 ? node->next : node->prev; + + pos += direc; + } + + return node; +} + +int llist_get(llist_t *list, unsigned int index) { + /* Get node */ + node_t *node = llist_get_node(list, index); + if( node == NULL ) { + /* Yes i know this is stupid */ + return -1; + } + + /* Return value */ + return node->val; +} + + +int llist_pop(llist_t *list, unsigned int index) { + /* Get node */ + node_t *node = llist_get_node(list, index); + if( node == NULL ) { + /* Yes i know this is stupid */ + return -1; + } + + /* Update root and head if we delete it */ + if( node == list->root ) { + list->root = node->next; + } + if( node == list->head ) { + list->head = node->prev; + } + + /* Keep len up to date */ + list->len--; + + /* Delete stuff */ + return node_pop(node); +} diff --git a/sem1/algo/mm2/linked/llist.h b/sem1/algo/mm2/linked/llist.h new file mode 100644 index 0000000..e52be89 --- /dev/null +++ b/sem1/algo/mm2/linked/llist.h @@ -0,0 +1,22 @@ +#ifndef LIST_H +#define LIST_H + +#include "node.h" + +typedef struct { + node_t *root; + node_t *head; + unsigned int len; +} llist_t; + +void llist_init(llist_t *list); + +void llist_append(llist_t *list, int val); + +node_t *llist_get_node(llist_t *list, unsigned int index); + +int llist_get(llist_t *list, unsigned int index); + +int llist_pop(llist_t *list, unsigned int index); + +#endif diff --git a/sem1/algo/mm2/linked/main.c b/sem1/algo/mm2/linked/main.c new file mode 100644 index 0000000..72b62cc --- /dev/null +++ b/sem1/algo/mm2/linked/main.c @@ -0,0 +1,45 @@ +#include <stdio.h> +#include "node.h" +#include "llist.h" + +void list_print(node_t *root) { + int index = 0; + /* Loop through notes and print them */ + while( root != NULL ) { + /* Print a value */ + printf("%d: %d\n", index++, root->val); + + /* Next value */ + root = root->next; + } +} + +/* Remove node */ +int main() { + + /* Do some stuff */ + llist_t list; + llist_init(&list); + + llist_append(&list, 11); // 0 + llist_append(&list, 22); // 1 + llist_append(&list, 33); // 2 + llist_append(&list, 44); // 3 + llist_append(&list, 89); // 4 + llist_append(&list, 12); // 5 + llist_append(&list, 2); // 6 + llist_append(&list, 1); // 7 + llist_append(&list, 7); // 8 + llist_append(&list, 232);// 9 + + list_print(list.root); + printf("%d\n", llist_get(&list, 5)); + llist_pop(&list, 9); + printf("%d\n", llist_get(&list, 7)); + + list_print(list.root); + + while( list.len ) { + printf("Popped %d\n", llist_pop(&list, 0)); + } +} diff --git a/sem1/algo/mm2/linked/node.c b/sem1/algo/mm2/linked/node.c new file mode 100644 index 0000000..cce1be0 --- /dev/null +++ b/sem1/algo/mm2/linked/node.c @@ -0,0 +1,57 @@ +#include "node.h" + +#include <string.h> +#include <stdlib.h> + +/* Insert after node */ +node_t *node_insert(node_t *node, int val) { + /* Create new node */ + node_t *newNode = (node_t *) malloc( sizeof(node_t) ); + if( newNode == NULL ) { + return NULL; + } + + + newNode->val = val; + newNode->prev = node; + + /* Check if there is node before */ + if( node == NULL ) { + /* If not then there is no after */ + newNode->next = NULL; + return newNode; + } + + /* Set next node */ + newNode->next = node->next; + node->next = newNode; + + /* Check node after */ + if( newNode->next != NULL ) { + /* Backlink next node */ + newNode->next->prev = newNode; + } + + return newNode; +} + +/* Pop node */ +int node_pop(node_t *node) { + int val = node->val; + + /* Check prev */ + if( node->prev != NULL ) { + /* Point last node to next node */ + node->prev->next = node->next; + } + + /* Check next */ + if( node->next != NULL ) { + node->next->prev = node->prev; + } + + /* Free memory */ + free(node); + + return val; +} diff --git a/sem1/algo/mm2/linked/node.h b/sem1/algo/mm2/linked/node.h new file mode 100644 index 0000000..027926b --- /dev/null +++ b/sem1/algo/mm2/linked/node.h @@ -0,0 +1,23 @@ +#ifndef NODE_H +#define NODE_H + +typedef struct node_struct { + int val; + struct node_struct *next; + struct node_struct *prev; +} node_t; + +/** @brief Create a new node after specified node + * + * @param node Pointer to node where new node should be inserted, can also be NULL + * @param val Value to add to new node + */ +node_t *node_insert(node_t *node, int val); + +/** @brief Pop node from chain and free's the resource + * + * @return Value in node + */ +int node_pop(node_t *node); + +#endif diff --git a/sem1/algo/mm2/queue.c b/sem1/algo/mm2/queue.c new file mode 100644 index 0000000..a93f76a --- /dev/null +++ b/sem1/algo/mm2/queue.c @@ -0,0 +1,100 @@ +#include <stdio.h> +#include <string.h> +#include <stdlib.h> + +#define EFULL 2 +#define EMPTY 3 + +/* Queue stuff */ +typedef struct { + int head; + int tail; + int len; + int cap; + int *buff; +} queue_t; + +/* Queue functions */ +int queue_init(queue_t *q, size_t cap) { + /* Make the struct and set i to zero */ + memset(q, 0, sizeof(queue_t)); + + /* Allocate the buffer */ + q->buff = (int *) malloc(cap * sizeof(int)); + if( q->buff == NULL ) { + return 1; + } + + /* Set capacity, the rest should be zero form memset */ + q->cap = cap; + return 0; +} + +void queue_free(queue_t *q) { + /* Free the heap buffer */ + free(q->buff); +} + +int queue_place(queue_t *q, int val) { + /* Check if full */ + printf("len: %d\n", q->len); + if( q->len >= q->cap) { + printf("ERR: Full\n"); + return EFULL; + } + + /* Add to queue */ + q->buff[q->head] = val; + + /* Increase values */ + q->head = (q->head+1) % q->cap; + q->len++; + + return 0; +} + +int queue_get(queue_t *q, int *val) { + /* Check if empty */ + if( !q->len ) { + printf("ERR: Empty\n"); + return EMPTY; + } + + /* Read value */ + if( val != NULL ){ + *val = q->buff[q->tail]; + } + + /* Decrease values */ + q->tail = (q->tail+1) % q->cap; + q->len--; + + return 0; +} + +int main(void) { + int in; + char com; + + queue_t q; + queue_init(&q, 16); + + for(;;) { + /* Read a command */ + scanf("%c", &com); + + if( com == 'w') { + printf("> "); + scanf("%d", &in); + queue_place(&q, in); + } else if( com == 'r' ) { + queue_get(&q, &in); + printf("%d\n", in); + } else if( com == 'q' ) { + break; + } + } + + queue_free(&q); + +} diff --git a/sem1/algo/mm3/multiply.c b/sem1/algo/mm3/multiply.c new file mode 100644 index 0000000..e454de3 --- /dev/null +++ b/sem1/algo/mm3/multiply.c @@ -0,0 +1,56 @@ +#include <stdio.h> +#include <stdlib.h> +#include <stdint.h> +#include <time.h> + +uint64_t mult(uint64_t x, uint64_t y, unsigned int bits) { + /* Check if they expect more than 64 bits. */ + if( bits > 64 ) { + printf("Sorry we cant handle higher than 64 bits\n"); + exit(1); + } else if(bits <= 1) { + return x && y; + } + + unsigned int newBits = bits >> 1; + +#if DO_PRINT == 1 + printf("\n\n bits: %u, New bits: %u\n", bits, newBits); +#endif + + /* Split up into to */ + uint32_t halvMask = ((uint64_t)1 << newBits) - 1; +#if DO_PRINT == 1 + printf("Using mask 0x%08X\n", halvMask); +#endif + uint32_t a = (x >> (newBits)) & halvMask; + uint32_t b = x & halvMask; + uint32_t c = (y >> (newBits)) & halvMask; + uint32_t d = y & halvMask; + +#if DO_PRINT == 1 + printf("A: 0x%08X, B: 0x%08X, C: 0x%08X, D: 0x%08X\n", a, b, c, d); +#endif + + return (mult(a, c, newBits) << bits) + ((mult(a, d, newBits) + mult(b, c, newBits)) << newBits) + mult(b, d, newBits); + +} + + +int main(void) { + + uint32_t a = 0xFFFFFF; + uint8_t b = 55; + uint64_t res; + + clock_t begin = clock(); + res = mult(a, b, 64); + clock_t end = clock(); + + printf("Result: %lld\n", res); + + clock_t diff = end - begin; + printf("Took %d which is %f s\n", diff, (double)diff/CLOCKS_PER_SEC); + + return 0; +} diff --git a/sem1/algo/mm3/opgaver.md b/sem1/algo/mm3/opgaver.md new file mode 100644 index 0000000..a6e560c --- /dev/null +++ b/sem1/algo/mm3/opgaver.md @@ -0,0 +1,49 @@ +# Opgave 1 + +## Exercise 9.2 + +**T(n) = 3T(n/2) + n** + +a = 3 +b = 2 +d(n) = n + +a ? d(b) -> 3 > 2 + +Svaret er derfor O(n^log2(3)) = O(n^1.59) + +**T(n) = 3T(n/2) + n^2** + +3 ? 2^2 -> 3 < 4 + +d(n) = n^2 hvilket betyder at O(n^2) + +**T(n) = 8T(n/2) + n^2** + +8 ? 2^3 -> 8 = 8 + +d(n) = n^3 hvilket betyder at O(n^3 log2(n)) + +## Evercise 9.3 + +**T(n) = 4T(n/3) + n** + +a = 4 +b = 3 +d(n) = n + +4 ? 3 -> 4 > 3 + +Derfor er svaret O(n^log3(4)) = O(n^1.26) + +**T(n) = 4T(n/3) + n^2** + +4 ? 3^2 -> 4 < 9 + +d(n) = n^2 hvilket betyder at O(n^2) + +**T(n) = 9T(n/3) + n^2** + +9 ? 3^2 -> 9 = 9 + +d(n) = n^2 hvilket betyder at O(n^2 log2(n)) diff --git a/sem1/module.c b/sem1/module.c new file mode 100644 index 0000000..3a25d25 --- /dev/null +++ b/sem1/module.c @@ -0,0 +1,12 @@ +#include <linux/init.h> +#include <linux/kernel.h> +#include <linux/module.h> + +module_init(void) { + printk(KERN_INFO "COOL_MODULE: Hej med dig\n"); + return 0; +} + +module_exit(void) { + printk(KERN_INFO "COOL_MODULE: Nou moe\n"); +} diff --git a/sem1/osc/mm1/.gitignore b/sem1/osc/mm1/.gitignore new file mode 100644 index 0000000..b18a498 --- /dev/null +++ b/sem1/osc/mm1/.gitignore @@ -0,0 +1,10 @@ +jmod.ko +.jmod.ko.cmd +jmod.mod.c +jmod.mod.o +.jmod.mod.o.cmd +jmod.o +.jmod.o.cmd +modules.order +Module.symvers +.tmp_versions diff --git a/sem1/osc/mm1/mm1/Makefile b/sem1/osc/mm1/mm1/Makefile new file mode 100644 index 0000000..13c8e62 --- /dev/null +++ b/sem1/osc/mm1/mm1/Makefile @@ -0,0 +1,7 @@ +obj-m += jmod.o + +all: + make -C /lib/modules/$(shell uname -r)/build M=$(shell pwd) modules +clean: + make -C /lib/modules/$(shell uname -r)/build M=$(shell pwd) clean + diff --git a/sem1/osc/mm1/mm1/Readme.md b/sem1/osc/mm1/mm1/Readme.md new file mode 100644 index 0000000..fcc6cb3 --- /dev/null +++ b/sem1/osc/mm1/mm1/Readme.md @@ -0,0 +1,34 @@ +# Opgaver til operativ systemer + +Ligenu er det ikke delt op i mapper. + +## Kør mini kernel modul + +Compile med make. +Husk at peg makefile på din kernel modul mappe. +Denne er testet på ubuntu server 19.04. + +``` +make +``` + +Nu burde der være kommet et jmod.ko som kan loades med. + +``` +sudo insmod jmod.ko +``` + +Hvis du får permission denied kan du få flere information ved at checke `dmesg` loggen. + +Nu kan du hente major number ind fra dmesg. Led efter `COOL_MODULE:`. +Dette nummer bruger du til at assign den en node + +``` +sudo mknod /dev/cooldev c MAJOR 0 +``` + +Dette vil map kernel-modul/driver til cooldev i /dev/ mappen. +Husk at skriv til MAJOR nummer fra `dmesg` i stedet for MAJOR. + +Hvis man læser man pagen kan man se at det bliver lavet som en character unbuffered file. +MINOR nummeret er 0 da vores driver alligevel ikke bruger det til noget. diff --git a/sem1/osc/mm1/mm1/jmod.c b/sem1/osc/mm1/mm1/jmod.c new file mode 100644 index 0000000..a07077c --- /dev/null +++ b/sem1/osc/mm1/mm1/jmod.c @@ -0,0 +1,70 @@ +#include <linux/kernel.h> +#include <linux/module.h> +#include <linux/init.h> +#include <linux/fs.h> +#include <asm/uaccess.h> + +static int major_num; +static int busy; + + +static int cool_open(struct inode *inode, struct file *file) { + /* Check if we are already serving someone */ + if (busy) { + return -EBUSY; + } + + busy = 1; + return 0; +} + +static int cool_release (struct inode *inode, struct file *file) { + busy = 0; + + return 0; +} + +static ssize_t cool_read (struct file *filp, char *buffer, size_t len, loff_t *offset) { + + char str[12] = "hej med dig"; + int i; + + for (i = 0; i < len; i++) { + put_user(str[i % 12], buffer++); + } + + return i; +} + +static struct file_operations file_ops = { + .owner = THIS_MODULE, + .read = cool_read, + .open = cool_open, + .release = cool_release +}; + +static int __init jmod_init(void) +{ + printk(KERN_INFO "COOL_MODULE: Registering cooldev\n"); + + major_num = register_chrdev(0, "cooldev", &file_ops); + if (major_num < 0) { + printk(KERN_ERR "COOL_MODULE: Could not register major\n"); + return 1; + } + + printk(KERN_INFO "COOL_MODULE: Got major %d\n", major_num); + + return 0; +} + + +static void __exit jmod_exit(void) +{ + printk(KERN_INFO "COOL_MODULE: Nou moe\n"); + unregister_chrdev(major_num, "cooldev"); +} + +module_init( jmod_init ); +module_exit( jmod_exit ); + diff --git a/sem1/osc/mm1/mm2/tprog.c b/sem1/osc/mm1/mm2/tprog.c new file mode 100644 index 0000000..377555f --- /dev/null +++ b/sem1/osc/mm1/mm2/tprog.c @@ -0,0 +1,71 @@ +#include <signal.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <sys/time.h> + +#define STARTSEC 10 +#define ENDUSEC 500000 +#define SPEED 0.8 + +struct itimerval timer; + +void timer_handler(int signum) { + /* Handy structure reference */ + struct timeval *tv = &timer.it_value; + printf("Hey we hit the alarm\n\a"); + + /* Calculate new alarm */ + tv->tv_sec *= SPEED; + if (tv->tv_sec == 0) { + /* If tv_usec is 0 set i to 1 sec otherwise half it */ + if (tv->tv_usec == 0) { + tv->tv_usec = 999999; + } else if (tv->tv_usec > ENDUSEC) { + tv->tv_usec *= SPEED; + if (tv->tv_usec < ENDUSEC) { + tv->tv_usec = ENDUSEC; + } + } else { + /* Return letting the timer be set to ENDUSEC */ + return; + } + } + + printf("Set to %d and %d\n", timer.it_value.tv_sec, timer.it_value.tv_usec); + /* Set alarm */ + int err = setitimer(ITIMER_REAL, &timer, NULL); + if (err) { + printf("Hey we got an error guys\n"); + exit(1); + } +} + +int main() { + /* Setup handler for timer */ + struct sigaction sa; + memset(&sa, 0, sizeof(sa)); /* Remeber to set all fields to zero */ + + sa.sa_handler = &timer_handler; + sigaction(SIGALRM, &sa, NULL); + + /* Setup timer values */ + timer.it_value.tv_sec = STARTSEC; + timer.it_value.tv_usec = 0; + + timer.it_interval.tv_sec = 0; + timer.it_interval.tv_usec = ENDUSEC; + + /* Start the timer */ + setitimer(ITIMER_REAL, &timer, NULL); + + /* Select signals */ + sigset_t sigset; + sigemptyset(&sigset); + sigaddset(&sigset, SIGTERM); + + /* Wait for termination */ + sigwait(&sigset, NULL); + + return 0; +} diff --git a/sem1/osc/mm3/opgaver.md b/sem1/osc/mm3/opgaver.md new file mode 100644 index 0000000..d9440f8 --- /dev/null +++ b/sem1/osc/mm3/opgaver.md @@ -0,0 +1,47 @@ +# Opgave 1 + +> Et operativsystem anvenderen 2-level page tabel og 4Kbyte pagesize. Det +virtuelle adresseområde er på 4GByte. De programmer der afvikles på +computeren er på mellem 64 KByte og 16MByte. Hvor mange bit vil I anvende til +index ind i hhv. page tabel 1 og pagetabel 2. + +Her betyder det at man har en tabel der referere til level 2 tabeller. + +Så i level to tabellen ville jeg nok have 4M da det er 1023 pages. +Dette betyder at der vil lidt spild med det lille program på 64kb men det større program på 16Mb betøver ikke få så mange pages. + +1023 pages kræver tilgængeld 10 bits til indexering hvilket er lidt spild. + +For at få op til 4GB skal man igen have 1023 reference i level 1 tabel. + +En anden mulighed ville være at have 8 bits til level 2 index, og derfor have 255 pages i level to tabel. +Dette vil betyde at level to indexen ikke spilder plads from med 10 bit. + +En level 1 tabel indexer derfor 4Kb * 255 = 4096 * 255 = 104 4480 = 104Kb + +Her vil level 1 tabellen få 4Gb / 104.4480Kb = 4 000 000 000 / 104 4480 =~= 4112 + +Her skal man bruge 13 bits, hvilket betyder at man spilder 3 bits hvis man bruger 16 bit system. + +# Opgave 2 + +> Diskuter måder at håndtere virtuelle pages på. Kan man optimere software i +forhold til hvordan et OS håndterer pages? Er der noget i en eller flere +koncepter I måske kan anvende i jeres projekt? + +Læser på wikipedia at dette er en teknik hvor man gemmer under pagene i virtuel memory i stedet for physical. +Dette vil betyder at den også kan blive swappet til disk osv. + +Dette vil tilgengeld kræve at man har nogle pages i physical som skal holder styr på de virtuelle som indeholder andre pages. +Det vil nok egentlig være lidt bøvlet. + +Man kunne måske have at level 1 tabellen signalere om pagen er i physical eller virtuel. + +# Opgave 3 + +> Skriv et lille program, der allokerer en stadig voksende mængde hukommelse, +f.eks. start med 8kB, 8MB, 8GB og mere... hvornår løber I ind i problemer? +Observer evt. med værktøjet ovenstående eller andet der passer til jeres +platform. + + |