From 7d07ff825dc7cff7ee80b04346e0d2c49a91e190 Mon Sep 17 00:00:00 2001 From: scratko Date: Sun, 31 Mar 2024 21:05:36 +0300 Subject: Initial commit --- Makefile | 19 +++ README.md | 3 + arith_exp.c | 239 +++++++++++++++++++++++++++++++++++ arithmetic-expression-computator.png | Bin 0 -> 17449 bytes calls.asm | 77 +++++++++++ calls.h | 11 ++ stack.c | 68 ++++++++++ stack.h | 17 +++ start.asm | 14 ++ 9 files changed, 448 insertions(+) create mode 100644 Makefile create mode 100644 README.md create mode 100644 arith_exp.c create mode 100644 arithmetic-expression-computator.png create mode 100644 calls.asm create mode 100644 calls.h create mode 100644 stack.c create mode 100644 stack.h create mode 100644 start.asm 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 + + 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 Binary files /dev/null and b/arithmetic-expression-computator.png differ 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 -- cgit v1.2.3