Initial commit

9 files changed, 448 insertions, 0 deletions

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..4e837c8
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,19 @@
+CC=gcc
+CFLAGS=-c -Wall -fno-stack-protector -m32
+
+ASM=nasm
+ASMFLAGS=-f elf
+
+BUILDFLAGS=-m elf_i386
+
+all: arith_exp
+
+%.o: %.asm
+	$(ASM) $(ASMFLAGS) $< -o $@
+%.o: %.c %.h
+	$(CC) $(CFLAGS) $< -o $@
+
+OBJMODULES= start.o calls.o stack.o arith_exp.o
+
+arith_exp: $(OBJMODULES)
+	$(LD) $(BUILDFLAGS) $^ -o $@
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..979b020
--- /dev/null
+++ b/README.md
@@ -0,0 +1,3 @@
+# Arithmetic expression computator
+
+<img src="arithmetic-expression-computator.png" />
diff --git a/arith_exp.c b/arith_exp.c
new file mode 100644
index 0000000..8a4c002
--- /dev/null
+++ b/arith_exp.c
@@ -0,0 +1,239 @@
+#include "calls.h"
+#include "stack.h"
+#define BUF_SIZE 80
+
+char buffer[BUF_SIZE];
+
+enum { 
+    success     = 1,
+    error       = -1,
+    base        = 10
+};
+enum state { yes, no };
+
+static int is_higher_priority(const stack *operation_stack, 
+                              int current_operation)
+{
+    int prev_operation = top_stack(operation_stack);
+    return (prev_operation == '+' || prev_operation == '-') && 
+        (current_operation == '*' || current_operation == '/');
+}
+
+static void make_operation(stack *rpn_stack, int operation)
+{
+    long first_operand, second_operand, result;
+    second_operand = pop_stack(rpn_stack);
+    first_operand = pop_stack(rpn_stack);
+    switch(operation) {
+        case '+':
+            result = first_operand + second_operand;
+            break;
+        case '-':
+            result = first_operand - second_operand;
+            break;
+        case '*':
+            result = first_operand * second_operand;
+            break;
+        case '/':
+            result = first_operand / second_operand;
+            break;
+    }
+    push_stack(rpn_stack, result);
+}
+
+static long translate_to_number(const char *begin_address, int size, 
+                                enum state is_negative_number)
+{
+    long number = 0;
+    int i;
+    if(is_negative_number == yes)
+        ++begin_address;
+    for(i = 0; i < size; ++i)
+        number = number * base + (begin_address[i] - '0');
+    if(is_negative_number == yes) {
+        number = ~number;
+        ++number;
+    }
+    return number;
+}
+
+static int extract_digit(const char *buf, long *number, int buf_length, 
+                         int *pos)
+{
+    enum state is_negative_number = no;
+    enum state is_positive_number = no;
+    enum state is_end_negative_expression = no;
+    const char *begin_address;
+    int number_length = 0;
+    for( ; *pos < buf_length; ++*pos) {
+        if(buf[*pos] == '(' && *pos+1 < buf_length && buf[*pos+1] == '-') {
+            is_negative_number = yes;
+            begin_address = &buf[*pos+1];
+            ++*pos;
+            continue;
+        }
+        switch(buf[*pos]) {
+            case '(':
+                if(is_negative_number == no && is_positive_number == no)
+                    return '(';
+                else
+                    return error;
+            case ')':
+                if(is_negative_number == yes && 
+                    is_end_negative_expression == no)
+                {
+                    is_end_negative_expression = yes;
+                    continue;
+                }
+                *number = 
+                    translate_to_number(begin_address, number_length, 
+                                        is_negative_number == yes ? yes : no);
+                return ')';
+            case '+':
+            case '-':
+            case '*':
+            case '/':
+            case '\n':
+                if(is_negative_number == yes || is_positive_number == yes) {
+                    *number = translate_to_number(begin_address, number_length, 
+                        is_negative_number == yes ? yes : no);
+                    return success;
+                } else
+                    return error;
+        }
+        if(buf[*pos] >= '0' && buf[*pos] <= '9') {
+            if(is_negative_number == no && is_positive_number == no) {
+                begin_address = &buf[*pos];
+                is_positive_number = yes;
+            }
+            ++number_length;
+            continue;
+        }
+        return error;
+    }
+    return error;
+}
+
+static void clean_operation_stack(stack *operation_stack, stack *rpn_stack)
+{
+    int operation;
+    while(!is_empty_stack(operation_stack) && 
+        top_stack(operation_stack) != '(')
+    {
+        operation = pop_stack(operation_stack);
+        make_operation(rpn_stack, operation);
+    }
+    if(is_empty_stack(operation_stack))
+        sys_exit(2);
+    pop_stack(operation_stack);
+}
+
+static void print_number(stack *rpn_stack)
+{
+    enum { string_buffer_size = 20 };
+    long symbol;
+    char string[string_buffer_size];
+    int i = 0;
+    long number = pop_stack(rpn_stack);
+    if(number < 0) {
+        number = ~number;
+        ++number;
+        string[i] = '-';
+        ++i;
+    }
+    stack reverse_number;
+    init_stack(&reverse_number);
+    while(number) {
+        symbol = number % base;
+        symbol += '0';
+        push_stack(&reverse_number, symbol);
+        number /= base;
+    }
+    for( ; !is_empty_stack(&reverse_number) && i < string_buffer_size; ++i)
+        string[i] = pop_stack(&reverse_number);
+    if(i < string_buffer_size) {          /* new line  */
+        string[i] = '\n';
+        ++i;
+    }
+    sys_write(1, string, i);
+}
+
+static void buffer_process(const char* buffer, int length, stack *rpn_stack, 
+                           stack *operation_stack)
+{
+    int top, pos, result;
+    char symbol;
+    long operand;
+    pos = 0;
+    while(pos < length) {
+        result = extract_digit(buffer, &operand, length, &pos);
+        if(result == error)
+            sys_exit(1);
+        symbol = buffer[pos];
+        if(symbol == '(') {
+            push_stack(operation_stack, symbol);
+            ++pos;
+            continue;
+        }
+        if(symbol == '\n' || symbol == ')' || symbol == '+' || symbol == '-' || 
+            symbol == '*' || symbol == '/')
+        {
+            push_stack(rpn_stack, operand);
+        }
+        if(symbol == ')') {
+            clean_operation_stack(operation_stack, rpn_stack);
+            ++pos;
+            while(pos < length && buffer[pos] == ')') {
+                clean_operation_stack(operation_stack, rpn_stack);
+                ++pos;
+            }
+            if(pos >= length)
+                sys_exit(1);
+        }
+        switch(buffer[pos]) {
+            case '\n':
+                clean_operation_stack(operation_stack, rpn_stack);
+                if(is_empty_stack(operation_stack))
+                    print_number(rpn_stack);
+                else
+                    sys_exit(1);
+                return;
+            case '+':
+            case '-':
+            case '*':
+            case '/':
+                top = top_stack(operation_stack);
+                if(top == '(' || 
+                    is_higher_priority(operation_stack, buffer[pos])) {
+                    push_stack(operation_stack, buffer[pos]);
+                    ++pos;
+                    continue;
+                }
+                else {
+                    while(top_stack(operation_stack) != '(' && 
+                        !is_higher_priority(operation_stack, buffer[pos])) {
+                        make_operation(rpn_stack, pop_stack(operation_stack));
+                    }
+                    push_stack(operation_stack, buffer[pos]);
+                    ++pos;
+                }
+        }
+    }
+}
+
+int main()
+{
+    int length;
+    stack rpn_stack, operation_stack;
+    init_stack(&rpn_stack);
+    init_stack(&operation_stack);
+    push_stack(&operation_stack, '(');
+    length = sys_read(0, buffer, BUF_SIZE);
+    if(!length)         /* EOF */
+        return 0;
+    if(length == -1)    /* error  */
+        return 3;
+    buffer_process(buffer, length, &rpn_stack, &operation_stack);
+    sys_free(heap_base);
+    return 0;
+}
diff --git a/arithmetic-expression-computator.png b/arithmetic-expression-computator.png
new file mode 100644
index 0000000..37a6e99
--- /dev/null
+++ b/arithmetic-expression-computator.png
diff --git a/calls.asm b/calls.asm
new file mode 100644
index 0000000..7d45fa7
--- /dev/null
+++ b/calls.asm
@@ -0,0 +1,77 @@
+global sys_write
+global sys_read
+global sys_errno
+global sys_alloc
+global sys_free
+global sys_exit
+
+section .text
+
+generic_sys_call_3:
+		push ebp
+		mov ebp, esp
+		push ebx
+		mov ebx, [ebp+8]
+		mov ecx, [ebp+12]
+		mov edx, [ebp+16]
+		int 80h
+		mov edx, eax
+		and edx, 0fffff000h
+		cmp edx, 0fffff000h
+		jnz .okay
+		mov [sys_errno], eax
+		xor eax, eax
+		not eax			; -1
+.okay:		pop ebx
+		mov esp, ebp
+		pop ebp
+		ret
+
+sys_write:	mov eax, 4
+		jmp generic_sys_call_3
+sys_read:	mov eax, 3
+		jmp generic_sys_call_3
+
+sys_alloc:	push ebp
+		mov ebp, esp	
+		mov eax, 45		; brk()
+		xor ebx, ebx
+		int 80h
+		mov [initial_break], eax
+
+		mov eax, 45
+		mov ebx, [initial_break]
+		add ebx, [ebp+8]
+		int 80h
+		cmp eax, [initial_break]
+		jz .error
+		mov eax, [initial_break]
+		jmp .quit
+.error:		mov eax, -1
+.quit:		mov esp, ebp
+		pop ebp
+		ret
+
+sys_free:	push ebp
+		mov ebp, esp
+		mov eax, 45
+		mov ebx, [ebp+8]
+		int 80h
+		mov esp, ebp
+		pop ebp
+		ret
+
+sys_exit:	push ebp
+		mov ebp, esp
+		mov eax, 1
+		mov ebx, [ebp+8]
+		int 80h
+		mov esp, ebp
+		pop ebp
+		ret 
+
+section .bss
+sys_errno 	resd	1
+
+section .data
+initial_break	dd	0
diff --git a/calls.h b/calls.h
new file mode 100644
index 0000000..3e5ee24
--- /dev/null
+++ b/calls.h
@@ -0,0 +1,11 @@
+#ifndef CALLS_H_SENTRY
+#define CALLS_H_SENTRY
+
+int sys_write(int fd, const void *buf, int size);
+int sys_read(int fd, void *buf, int size);
+void* sys_alloc(int size);
+void sys_free(void* p);
+void sys_exit(int code);
+extern int sys_errno;
+
+#endif
diff --git a/stack.c b/stack.c
new file mode 100644
index 0000000..8aee3d7
--- /dev/null
+++ b/stack.c
@@ -0,0 +1,68 @@
+#include "stack.h"
+#include "calls.h"
+
+#define QUANTITY_ADDRESSES 5
+
+enum address_control { get_address, set_address };
+void* heap_base;
+
+void init_stack(stack *st)
+{
+    *st = 0;
+}
+
+static void* address_management(void* address, enum address_control state)
+{
+    enum { null = 0 };
+    static void* available_addresses[QUANTITY_ADDRESSES];
+    int i;
+    if(state == set_address) {
+        for(i = 0; i < QUANTITY_ADDRESSES; ++i) {
+            if(!available_addresses[i]) {
+                available_addresses[i] = address;
+                return null;
+            }
+        }
+        return null;
+    }
+    for(i = 0; i < QUANTITY_ADDRESSES; ++i) {
+        if(available_addresses[i]) {
+            address = available_addresses[i];
+            available_addresses[i] = 0;
+            return address;
+        }
+    }
+    return null;
+}
+
+
+void push_stack(stack *st, long num)
+{
+    struct item *tmp;
+    tmp = address_management(0, get_address);
+    if(!tmp)
+        tmp = sys_alloc(sizeof(struct item));
+    if(!heap_base)
+        heap_base = tmp;
+    tmp->data = num;
+    tmp->next = *st;
+    *st = tmp;
+}
+
+long pop_stack(stack *st)
+{
+    long num = (*st)->data;
+    address_management(*st, set_address);
+    *st = (*st)->next;
+    return num;
+}
+
+int is_empty_stack(const stack *st)
+{
+    return *st ? 0 : 1;
+}
+
+long top_stack(const stack *st)
+{
+    return (*st)->data;
+}
diff --git a/stack.h b/stack.h
new file mode 100644
index 0000000..f7d0cfb
--- /dev/null
+++ b/stack.h
@@ -0,0 +1,17 @@
+#ifndef STACK_H_SENTRY
+#define STACK_H_SENTRY
+
+struct item {
+    long data;
+    struct item *next;
+};
+typedef struct item* stack;
+
+void init_stack(stack *st);
+void push_stack(stack *st, long num);
+long pop_stack(stack *st);
+int is_empty_stack(const stack *st);
+long top_stack(const stack *st);
+extern void* heap_base;
+
+#endif
diff --git a/start.asm b/start.asm
new file mode 100644
index 0000000..b685867
--- /dev/null
+++ b/start.asm
@@ -0,0 +1,14 @@
+global _start
+extern main
+
+section .text
+_start:	mov eax, [esp]	; argc
+	mov edx, esp
+	add edx, 4	; argv
+	push edx
+	push eax
+	call main
+	add esp, 8
+	mov ebx, eax	; return value from main
+	mov eax, 1
+	int 80h