[大数据]Snail OS 开发进入新阶段，但遇到了大难题，还请有缘人给个见解

如下图，这个时钟在单线程时走时是正确的，为什么按照郑刚先生真相还原，实现多线程后，就走成了这样，而且这里按照真相还原实现了互斥。底下把源代码也贴出来了，望高手给个指点。画时钟的代码大约在973行。

// kernel.c create by ideal.

#define video_addr 0xe0000000
#define idt_start 0x7c00
#define NULL 0

#define out(port, data) asm volatile ("out %w1, %b0;"::"a"(data), "d"(port))
#define in(port) ({\
	unsigned char _res;\
	asm volatile("in %b1, %w2":"=a"(_res):"0"(_res), "d"(port));\
	_res;\
})

#define bcd2bin(data) ((data) = (((data)&0xf) + (((data)>>4)*10)))
#define sti() asm volatile ("sti");
#define cli() asm volatile ("cli");

// base data struct start.


extern int pp; // 56214 size x 143 y 130

extern int ii; // ? size x 102 y 126

typedef enum bool{
	false, true
}bool;

typedef struct three_byte {
	unsigned char a[3];
}__attribute__((packed)) three_byte;

typedef unsigned long long ui64;

typedef unsigned int ui32;
typedef unsigned short ui16;
typedef unsigned char ui8;

typedef int si32;
typedef short si16;
typedef char si8;

// base data struct end.

// global value start.

ui32 system_count = 0;

static char font_A[16] = {
	0x00, 0x18, 0x18, 0x18, 0x18, 0x24, 0x24, 0x24,
	0x24, 0x7e, 0x42, 0x42, 0x42, 0xe7, 0x00, 0x00,
};

typedef struct pos_count {
	unsigned int x;
	unsigned int y;
	unsigned int count;
}pos;

pos syspos = {0, 512, 0};
ui32 colour;

// global value end.

// memory manager start. @1
#define ELEM_MAX 4096
#define VIR_ADDR_START 0
#define VIR_ADDR_SIZE 0x80000000
#define PHY_ADDR_START 0
#define PHY_ADDR_SIZE 512 * 1024 * 1024

struct mem_elem {
	struct mem_elem* prev, *next;
	ui32 start, size, elem_used_flag;
};

struct mem_list {
	struct mem_elem head, tail;
};

struct mem_man {
	struct mem_list used, free;
};

struct mem_man vir_mem, phy_mem;

struct mem_elem mem_elem_array[ELEM_MAX];

// memory manager end. @2

// exception and interrupt handler

extern void divide_error(void);
extern void single_step(void);
extern void nmi(void);
extern void breakpoint(void);
extern void overflow(void);
extern void bounds_check(void);
extern void inval_opcode(void);
extern void device_not_available(void);
extern void double_fault(void);
extern void coprocessor_segment_overrun(void);
extern void invaild_tss(void);
extern void segment_not_present(void);
extern void stack_segment(void);
extern void general_protection(void);
extern void page_fault(void);
extern void coprocessor_error(void);
extern void reserved(void);

extern void rtc_interrupt(void);
extern void clock_interrupt(void);
extern void irq7_interrupt(void);
extern void keyboard(void);
extern void mouse_interrupt(void);

void divide_error_handler(void);
void single_step_handler(void);
void nmi_handler(void);
void breakpoint_handler(void);
void overflow_handler(void);
void bounds_check_handler(void);
void inval_opcode_handler(void);
void device_not_available_handler(void);
void double_fault_handler(void);
void coprocessor_segment_overrun_handler(void);
void invaild_tss_handler(void);
void segment_not_present_handler(void);
void stack_segment_handler(void);
void general_protection_handler(ui32 ret_address, ui32 error_code);
void page_fault_handler(unsigned int error_code);
void coprocessor_error_handler(void);
void reserved_handler(void);

void rtc_handler(void);
void clock_interrupt_handler(void);
void irq7_interrupt_handler(void);
void keyboard_handler(void);
void mouse_interrupt_handler(void);

void init_8259(void);
void init_rtc(void);
void init_8253(void);
void wait_kbc_sendready(void);
void init_keyboard(void);
void enable_mouse(void);

void paint_rectangle(unsigned int x_left, unsigned int y_left, 
						unsigned int xsize,  unsigned int ysize, unsigned int colour);
void paint_char(unsigned int x_left, unsigned int y_top, 
				unsigned int colour, char *font);
void paint_str_black(unsigned int x_left, unsigned int y_top, 
				unsigned int colour, char* str);
void paint_str(unsigned int x_left, unsigned int y_top, 
				unsigned int colour, char* str);
void kprintf(const char* format_char, ...);
unsigned int mydiv(unsigned int* i, unsigned int n);
unsigned int mystrlen(char* s);	
char* i2a(unsigned int i, unsigned int n);
void paint_line(int start_x, int start_y, int end_x, int end_y, unsigned int colour);
void paint_point(int x, int y, unsigned int colour);
void paint_circle(int x_center, int y_center, int r, unsigned int colour);
void paint_circle0(int x_center, int y_center, int r, unsigned int colour);
void draw_circle_point(int x0, int y0, int x, int y, unsigned int colour);
void middle_point_circle(int x0, int y0, int r, unsigned int colour);
void paint_rectangle0(int xs, int ys, int xsize, int ysize, unsigned int colour);

void fillcircle(int x0, int y0, int r, unsigned int colour);

unsigned int getcolour(int x, int y);
void floodfill4(int x, int y, unsigned int oldcolour, unsigned int newcolour);
void buf_copy(char* s, char* d, unsigned int l);

ui64 create_gate(ui32 offset, ui16 selector, ui16 attrib);
void install_gate(ui16 num, ui32 offset, ui16 selector, ui16 attrib);
void divide_error_handler(void);
void init_exception_interrupt(void);

void* test(void);

// string start.

void mem_set(void* d, unsigned char value, unsigned int len);

// string end.

// bitmap start.

struct bit_map {
	unsigned char* start;
	unsigned int byte_size;
};

void init_bit_map(struct bit_map* map);
bool bit_check(struct bit_map* map, unsigned int bit_index);
void bit_set(struct bit_map* map, unsigned char value, unsigned int bit_index);
unsigned int find_counts_zero_bit(struct bit_map* map, unsigned int bit_counts);

// bitmap end.

// eflags start.

#define _IF_BIT (1 << 9) // 0x00000200
bool __cli(void);
bool __sti(void);

// eflags end.

// interrupt status start.

#define EFLAGS_IF 0x00000200
#define GET_EFLAGS(EFLAG_VAR) __asm__ volatile("pushf;pop %0":"=g"(EFLAG_VAR))

enum intr_status {
	INTR_OFF,
	INTR_ON
};

enum intr_status intr_enable(void);
enum intr_status intr_disable(void);
enum intr_status intr_set_status(enum intr_status status);
enum intr_status intr_get_status(void);

// interrupt status end.

// assert and panic start.

void _panic(const char* basefile, const char* filename,
			const char* func, unsigned int line, 
			const char* exp);
#define _assert(exp) if(exp); \
		else _panic(__BASE_FILE__, __FILE__, __func__, __LINE__, #exp);

// assert and panic end.


// sin and cos table start. sin value * 10000
static int sin_tab[60] = {
	0, 1045, 2079, 3090, 4067, 5000, 5878, 6691,
	7431, 8090, 8660, 9135, 9511, 9781, 9945,
	10000, 9945, 9781, 9511, 9135, 8660, 8090, 7431,
	6691, 5878, 5000, 4067, 3090, 2079, 1045,
	0, -1045, -2079, -3090, -4067, -5000, -5878, -6691,
	-7431, -8090, -8660, -9135, -9511, -9781, -9945,
	-10000, -9945, -9781, -9511, -9135, -8660, -8090, -7431,
	-6691, -5878, -5000, -4067, -3090, -2079, -1045
}; 

static int cos_tab[60] = {
	10000, 9945, 9781, 9511, 9135, 8660, 8090, 7431,
	6691, 5878, 5000, 4067, 3090, 2079, 1045,
	0, -1045, -2079, -3090, -4067, -5000, -5878, -6691,
	-7431, -8090, -8660, -9135, -9551, -9781, -9945,
	-10000, -9945, -9781, -9511, -9135, -8660, -8090, -7431,
	-6691, -5878, -5000, -4067, -3090, -2079, -1045,
	0 , 1045, 2079, 3090, 4067, 5000, 5878, 6691,
	7431, 8090, 8660, 9135, 9511, 9781, 9945
}; 

// sin and cos table end.





// first in first out start.

struct fifo32 {
	int next_w, next_r, size, free, flags;
	unsigned int* buf;
};

void init_fifo32(struct fifo32* fifo, int size,
				unsigned int* buf);
int fifo32_put(struct fifo32* fifo, unsigned int data);
unsigned int fifo32_get(struct fifo32* fifo);
int fifo32_status(struct fifo32* fifo);

unsigned int fifo_buf[1024];
struct fifo32 _fifo;

// first in first out end.


// paint clock start.

struct crt_data {
	ui8 hour;
	ui8 minute;
	ui8 second;
}__attribute__((packed));

struct crt_data crt_data = {0, 0, 0};

ui16 my_hour, my_minute, my_second;
unsigned int clock_flag = 0;
unsigned int c_f = 0;

ui32 system_count1 = 0;

void paint_clock(unsigned int x, unsigned int y);
void create_clock(unsigned int x, unsigned int y);
void start_clock(unsigned int x, unsigned int y) ;
void start_clock1(unsigned int x, unsigned int y);

// paint clock end

// task start.

int ta = 0, tb = 0, tc = 0;

void taska(void);
void taskb(void);
void taskc(void);

// task end.




// old string, bitmap, memory manager start.

void _memset(void* d, unsigned char value, unsigned int size);
void _memcpy(void* d, void* s, unsigned int size);

struct bitmap {
	unsigned int btmp_bytes_len;
	unsigned char* bits;
};

void bitmap_init(struct bitmap* btmp);
bool bitmap_scan_test(struct bitmap* btmp, unsigned int bit_idx);
int bitmap_scan(struct bitmap* btmp, unsigned int cnt);
void bitmap_set(struct bitmap* btmp, unsigned int bit_idx, signed char value);

// memory start.

struct virtual_addr {
	struct bitmap vaddr_bitmap;
	unsigned int vaddr_start;
};

struct pool {
	struct bitmap pool_bitmap;
	unsigned int phy_addr_start;
	unsigned int pool_size;
};

struct virtual_addr kernel_vaddr;
struct pool kernel_pool, user_pool;

static void mem_pool_init(unsigned int all_mem);
void mem_init(void);


// string 2 start.

void _strcpy(char* d, char* s);

// string 2 end.

// memory part 2 start.

enum pool_flags {
	PF_KERNEL = 1,
	PF_USER = 2
};

#define PDE_IDX(vaddr) (((vaddr) & 0xffc00000) >> 22)
#define PTE_IDX(vaddr) (((vaddr) & 0x003ff000) >> 12)

unsigned int* pte_ptr(unsigned int vaddr);
unsigned int* pde_ptr(unsigned int vaddr);

unsigned int* pte_ptr1(unsigned int vaddr);
unsigned int* pde_ptr1(unsigned int vaddr);
static void* vaddr_get(enum pool_flags pf, unsigned int pg_cnt);
static void* palloc(struct pool* m_pool);
static void page_table_add(void* _vaddr, void* _page_phyaddr);
void* malloc_page(enum pool_flags pf, unsigned int pg_cnt);
void* get_kernel_pages(unsigned int pg_cnt);



// memory part 2 end.


// memory end.

// old string, bitmap, memory manager end.

// list start.

#define offset(struct_type, member) (int)(&((struct_type*)0)->member)
#define elem2entry(struct_type, struct_member_name, elem_ptr) \
		(struct_type*)((int)elem_ptr - offset(struct_type, struct_member_name))

typedef void thread_func(void*);

enum task_status {
	TASK_RUNNING,
	TASK_READY,
	TASK_BLOCKED,
	TASK_WAITING,
	TASK_HANGING,
	TASK_DIED
};

struct intr_stack {
	unsigned int vec_no;
	unsigned int edi;
	unsigned int esi;
	unsigned int ebp;
	unsigned int esp_dummy;
	unsigned int ebx;
	unsigned int edx;
	unsigned int ecx;
	unsigned int eax;
	unsigned int gs;
	unsigned int fs;
	unsigned int es;
	unsigned int ds;
	
	unsigned int err_code;
	void (*eip)(void);
	unsigned int cs;
	unsigned int eflags;
	void* esp;
	unsigned int ss;
};

struct thread_stack {
	unsigned int edi;
	unsigned int esi;
	unsigned int ebp;
//	unsigned int esp;
	unsigned int ebx;
//	unsigned int edx;
//	unsigned int ecx;
//	unsigned int eax;
	
	void (*eip) (thread_func* func, void* func_arg);
	
	void (*unused_retaddr);
	thread_func* function;
	void* func_arg;
};





struct list_elem {
	struct list_elem* prev;
	struct list_elem* next;
};

struct list {
	struct list_elem head;
	struct list_elem tail;
};

typedef bool (function)(struct list_elem*, int arg);

void list_init(struct list* list);
void list_insert_before(struct list_elem* before, struct list_elem* elem);
void list_push(struct list* plist, struct list_elem* elem);
void list_append(struct list* plist, struct list_elem* elem);
void list_remove(struct list_elem* pelem);
struct list_elem* list_pop(struct list* plist);
bool elem_find(struct list* plist, struct list_elem* obj_elem);
struct list_elem* list_traversal(struct list* plist, function func, int arg);
unsigned int list_len(struct list* plist);
bool list_empty(struct list* plist);
// list end.



struct task_struct {
	unsigned int* self_kstack;
	enum task_status status;
	char name[64];
	unsigned char priority;
	unsigned char ticks;
	unsigned int elapsed_ticks;
	struct list_elem general_tag;
	struct list_elem all_list_tag;
	unsigned int* pgdir;
	unsigned int stack_magic;
};

struct task_struct* main_thread;
struct list thread_ready_list;
struct list thread_all_list;
static struct list_elem* thread_tag;

extern void switch_to(struct task_struct* cur, struct task_struct* next);

struct task_struct* running_thread(void);
static void kernel_thread(thread_func* function, void* func_arg);
void thread_create(struct task_struct* pthread,
			thread_func function, void* func_arg);
void init_thread(struct task_struct* pthread, char* name, int proi);
struct task_struct* thread_start(char* name,
								int proi,
								thread_func function,
								void* func_arg);
static void make_mian_thread(void);

unsigned int ticks;

void intr_timer_handler(void);
void schedule(void) ;
void thread_init(void);




void k_thread_a(void* arg);
void k_thread_b(void* arg);

// ipc start.

void thread_block(enum task_status stat);

void thread_unblock(struct task_struct* pthread);

// sync start.
struct semaphore {
	unsigned char value;
	struct list waiters;
};

struct lock {
	struct task_struct* holder;
	struct semaphore semaphore;
	unsigned holder_repeat_nr;
};

void sema_init(struct semaphore* psema, unsigned char value);
void lock_init(struct lock* plock);
void sema_down(struct semaphore* psema);
void sema_up(struct semaphore* psema);
void lock_acquire(struct lock* plock);
void lock_release(struct lock* plock);
static struct lock console_lock;
void console_init(void);
void console_acquire(void) ;
void console_release(void);
void console_put_str(char* s);
void console_put_char(unsigned char c);
void console_put_int(unsigned int i);



// sync end.

// ipc end.


// ioqueue start.

struct ioqueue {
	struct lock lock;
	struct task_struct* producer;
	struct task_struct* consumer;
	char buf[64];
	unsigned int head;
	unsigned int tail;
};

void ioqueue_init(struct ioqueue* ioq);
static unsigned int next_pos(unsigned int pos);
bool ioq_full(struct ioqueue* ioq);
static bool ioq_empty(struct ioqueue* ioq);
static void ioq_wait(struct task_struct** waiter);
static void wakeup(struct task_struct** waiter);
char ioq_getchar(struct ioqueue* ioq);
void ioq_putchar(struct ioqueue* ioq, char byte);

struct ioqueue kbd_buf;

void lock_clock(void);
void lock_clock1(void);
// ioqueue end.




void paint_picture1(unsigned int x_left, unsigned int y_bottom, 
					unsigned int xsize, unsigned int ysize);
					
void paint_picture2(unsigned int x_left, unsigned int y_bottom, 
					unsigned int xsize, unsigned int ysize, int* x);
					
					
					void draw_bmp(char* bmp, int x, int y);

int kernel_main(void) {
	
	init_exception_interrupt();
	
	int i, j;

	init_fifo32(&_fifo, 1024, fifo_buf);

	paint_rectangle(0, 0, 1024, 512,  0x2894ff);

	paint_rectangle(0, 512, 1024, 256, 0x000000);


/*	
	paint_circle(300, 300, 80, 0x2894ff); 
	

	for(i = 0; i < 31; i++) {
		kprintf("\n");		
	}

	for(i = 0; i < 127; i++) {
		kprintf("A");
	}


	paint_line(0, 0, 1024, 512, 0xffffff);
	paint_line(0, 512, 1024, 0, 0xffffff);
	paint_line(0, 512, 512, 0, 0x000000);
	
	paint_line(512, 0, 512, 256, 0xff0000);






	kprintf("%d", syspos.count);
	
	
	kprintf("%d", syspos.count);
	
	paint_point(20, 20, 0x000000);
	

	
	i = 0;
	for(i = 0; i < 10; i++) {
		paint_circle0(10 + i * 50 , 400, 10 + i , 0xff0000); 		
	}




	
	middle_point_circle(120, 120, 80, 0xffffff);

	paint_rectangle0(50, 50, 100, 200, 0x000000);

	paint_rectangle(173, 122, 50, 20, 0x000000);


	paint_circle(400, 300, 60, 0x0000ff);

	

	paint_rectangle0(800, 20, 40, 60, 0x000000);

//	buf_copy((char*)video_addr, (char*)video_addr, 1024 * 768 * 3);		
	
//	floodfill4(800 + 1, 20 + 1, 0x2894ff, 0xff0000);


	
	kprintf("The Snail OS is strating... %s @@%d@@%d@@", "Please waiting for time...", syspos.x, syspos.y );
	
	kprintf("\n Hello Wrold!\n The background colour is  %x \n ", getcolour(0, 0));



	paint_char(600, 600, 0xffffff, font_A);
	paint_str(500, 500, 0xffee00, "snail OS!");
	
	
	kprintf("\n Hello Wrold!\n %x " , sizeof(unsigned long long));	
	
*/	
	mem_init();
	
	get_kernel_pages(1);
	
	get_kernel_pages(2);

	get_kernel_pages(1);

	get_kernel_pages(100);	
	
	thread_init();

	kprintf(" %x ", pde_ptr(0x80400000));
	kprintf(" %x \n", pte_ptr(0x80400000));
	
	kprintf(" %x ", pde_ptr1(0x80400000));
	kprintf(" %x \n", pte_ptr1(0x80400000));
	
	init_8259();
	init_rtc();
	init_8253();
	init_keyboard();
	enable_mouse();
	
	console_init();
	ioqueue_init(&kbd_buf);
	
	out(0x21, 0xf8);
	out(0xa1, 0xee);
	
	
	unsigned char buf[4];
	buf[0] = 8;
	buf[1] = 0xc0;
	struct bit_map my_map;
	my_map.start = buf;
	my_map.byte_size = 4;
	
	for(i = 0; i < 4; i++)
	kprintf(" %b ", buf[i]);

	
	init_bit_map(&my_map);
	
	
	bit_set(&my_map, 1, 3);
	bit_set(&my_map, 0, 14);
	bit_set(&my_map, 1, 15);
	
	buf[0] = 0xf;
	
	kprintf("\n %d  \n", find_counts_zero_bit(&my_map, 10));

	for(i = 0; i < 4; i++)
	kprintf(" %b ", buf[i]);

	bit_set(&my_map, 1, 16);

	for(i = 0; i < 32; i++)
		bit_set(&my_map, 1, i);

	bit_set(&my_map, 0, 11);

	kprintf("\n %d  \n", find_counts_zero_bit(&my_map, 1));

	for(i = 0; i < 4; i++)
	kprintf(" %b ", buf[i]);



//	paint_picture2(500, 500, 184, 197, &ii);
	
//	paint_picture2(800, 200, 143, 130, &pp);	

	draw_bmp((char*) &pp, 703, 400);

	draw_bmp((char*) &ii, 2, 400);
	
	
	

	thread_start("k_thread_a", 2, k_thread_a, "argA ");
//	thread_start("k_thread_b", 1, k_thread_b, "argB ");	
	sti();

	

	unsigned int buf_data;
	while(1) {
		__asm__ __volatile__ ("cli");
		if(!fifo32_status(&_fifo)) {
			__asm__ __volatile__ ("sti;""hlt");
		} {
			unsigned int data = fifo32_get(&_fifo);
			if(data == 0xffff) {
//				paint_clock(200, 200);				
			}
			__asm__ __volatile__ ("sti");
		}

//		kprintf(" Main ");
		__cli();
		if(!ioq_empty(&kbd_buf)) {
			ioq_getchar(&kbd_buf);
			console_put_str(" @ ");			
		}
		__sti();
	};
}



void paint_picture2(unsigned int x_left, unsigned int y_bottom, 
					unsigned int xsize, unsigned int ysize,int* x) {
	char* p = (char*)(x);
	int flag = 0;
	int temp = xsize;
	if(temp * 3 % 4 != 0) {
		temp = temp * 3 + 4 - temp * 3 % 4;
	}
	int i, j;						
	for(j = y_bottom; j >= y_bottom - ysize; j--) {
			for(i = x_left; i < x_left + temp ; i++) {

			

			}	
	}											
}




struct bitmap_file_header {
	unsigned short bm;
	int file_size;
	unsigned short reserved1;
	unsigned short reserved2;
	int bitmap_offset;
}__attribute__((packed));

struct bmp_info_header {
	int i_size;
	long width;
	long height;
	short planes;
	short bitcount;
	int compression;
	int	image_size;
	long xpels;
	long ypels;
	int colour_used;
	int colour_improtant;
};



void draw_bmp(char* bmp, int x, int y) {
	struct bmp_info_header * p = (struct bmp_info_header *)(bmp + sizeof(struct bitmap_file_header));
	int width, height;
	width = p->width;
	height = p->height;
	int n;
	n = ((width * 3) % 4) == 0 ? 0 : (4 - (width * 3) % 4);
	char*q = (char*)((int)bmp + ((struct bitmap_file_header*)bmp)->bitmap_offset);
	unsigned char* bmp_buf = q;
//	unsigned int buf[width * height];
	unsigned int r, g, b;
	int i, j;
	unsigned int colour;
	
	for(i = y - 1; i >= y - height; i--) {
		for(j = x; j < x + width; j++) {
			b = *bmp_buf++;
			g = *bmp_buf++;
			r = *bmp_buf++;
			colour = (r << 16) | (g << 8) | b;
			paint_point(j, i, colour);
		}	
	}	
/*
	for(i = height - 1; i >= 0; i--) {
		for(j = 0; j < width; j++) {
			b = bmp_buf[3 * (width * i + j) + i * n];
			g = bmp_buf[3 * (width * i + j) + 1 + i * n];
			r = bmp_buf[3 * (width * i + j) + 2 + i * n];
//			buf[width * i + j] = a << 24 | r << 16 | g << 8 | b;
			((three_byte *)(video_addr + y * 1024 + x))[j + i * 1024].a[0] = b;
			((three_byte *)(video_addr + y * 1024 + x))[j + i * 1024].a[1] = g;
			((three_byte *)(video_addr + y * 1024 + x))[j + i * 1024].a[2] = r;				
		}
	}
*/	
}



void clock_interrupt_handler(void) {
	system_count1++;
	if(!(system_count1 & 0x0000000f)) {
		fifo32_put(&_fifo, 0xffff + 1);		
	}
	if(!(system_count1 & 0x0000003f)) {
		fifo32_put(&_fifo, 0xffff + 2);		
	}
	if(!(system_count1 & 0x0000007f)) {
		fifo32_put(&_fifo, 0xffff + 3);		
	}	
}

// paint clock start.

void paint_clock(unsigned int x, unsigned int y) {
	static unsigned int magic;
	if( magic == 0) {
		create_clock(x, y);		
	}
	magic++;
	start_clock1(x - 40, y);		
	start_clock(x, y);
}

// task start.

void taska(void) {
	kprintf("A %x ", ta++);
}

void taskb(void) {
	fillcircle(200,200, tb++ & 0x3f, tb << 13 | 0x231b0f);
}

void taskc(void) {
	kprintf("C %x ", tc++);	
}

// task end.

void create_clock(unsigned int x, unsigned int y) {
	int i;
	fillcircle(x, y, 103, 0x80c0ff);
	fillcircle(x, y, 99, 0x2894ff);

	int a, b;
	for(i = 0; i < 60; i++) {
		if(i % 15) {
		a = x + 95 * sin_tab[i] / 10000; 
		b = y - 95 * cos_tab[i] / 10000;
		paint_line (x, y, a, b , 0x000000);				
		}
	}
	
	fillcircle(x, y, 85, 0x2894ff);
	

	
	for(i = 0; i < 60; i++) {
		if(!(i % 5) && (i % 15)) {
		a = x + 95 * sin_tab[i] / 10000; 
		b = y - 95 * cos_tab[i] / 10000;
		paint_line (x, y, a, b , 0x000000);				
		}
	}

	fillcircle(x, y, 80, 0x2894ff);
	
	for(i = 0; i < 60; i++) {
		if((i % 15) == 0) {
		a = x + 80 * sin_tab[i] / 10000; 
		b = y - 80 * cos_tab[i] / 10000;
		paint_line (x, y, a, b , 0x000000);				
		}
	}
	
	fillcircle(x, y, 74, 0x2894ff);
	
	paint_str(x - 8, y - 94, 0xffffff, "12");
	paint_str(x - 4, y + 82, 0xffffff, "6");
	paint_str(x - 90, y - 8, 0xffffff, "9");
	paint_str(x + 86, y - 8, 0xffffff, "3");

}

void start_clock(unsigned int x, unsigned int y) {
	
}

void start_clock1(unsigned int x, unsigned int y) {	
	__asm__ ("cli");
	my_hour = bcd2bin(crt_data.hour);
	my_minute = bcd2bin(crt_data.minute);
	my_second = bcd2bin(crt_data.second);

	
	console_put_int(my_hour);
	console_put_int(my_minute);
	console_put_int(my_second);
		
	paint_rectangle(x, y, 90, 16,  0x2894ff);
	if(my_hour < 10) {
		paint_str(x, y, 0x000000, "0");
		paint_str(x + 8, y, 0x000000, i2a(my_hour, 10));		
	} else {
		paint_str(x, y, 0x000000, i2a(my_hour, 10));		
	}

	if(my_minute < 10) {
		paint_str(x + 30, y, 0x000000, "0");
		paint_str(x + 8 + 30, y, 0x000000, i2a(my_minute, 10));		
	} else {
		paint_str(x + 30, y, 0x000000, i2a(my_minute, 10));		
	}

	if(my_second < 10) {
		paint_str(x + 60, y, 0x000000, "0");
		paint_str(x + 8 + 60, y, 0x000000, i2a(my_second, 10));		
	} else {
		paint_str(x + 60, y, 0x000000, i2a(my_second, 10));		
	}
	
	
		int a, b;
	unsigned int _hour = my_hour;
	_hour %= 12;	
	if(c_f == clock_flag) {
		c_f++;
	}
	if(my_second == 0) {
		a = x + 72 * sin_tab[59] / 10000; 
		b = y - 72 * cos_tab[59] / 10000;
		paint_line (x, y, a, b , 0x2894ff);	
	}
	if(my_minute == 0) {
		a = x + 66 * sin_tab[59] / 10000; 
		b = y - 66 * cos_tab[59] / 10000;
		paint_line (x, y, a, b , 0x2894ff);	
	}
	if(_hour == 0) {
		a = x + 56 * sin_tab[59] / 10000; 
		b = y - 56 * cos_tab[59] / 10000;
		paint_line (x, y, a, b , 0x2894ff);			
	}
	if(c_f != clock_flag) {
		a = x + 72 * sin_tab[my_second - 1] / 10000; 
		b = y - 72 * cos_tab[my_second - 1] / 10000;
		paint_line (x, y, a, b , 0x2894ff);
		a = x + 66 * sin_tab[my_minute - 1] / 10000; 
		b = y - 66 * cos_tab[my_minute - 1] / 10000;
		paint_line (x, y, a, b , 0x2894ff);	
		a = x + 56 * sin_tab[_hour * 5 + my_minute / 12 - 1] / 10000; 
		b = y - 56 * cos_tab[_hour * 5 + my_minute / 12 - 1] / 10000;
		paint_line (x, y, a, b , 0x2894ff);				
	}
	a = x + 72 * sin_tab[my_second] / 10000; 
	b = y - 72 * cos_tab[my_second] / 10000;
	paint_line (x, y, a, b , 0xff0000);
	a = x + 66 * sin_tab[my_minute] / 10000; 
	b = y - 66 * cos_tab[my_minute] / 10000;
	paint_line (x, y, a, b , 0x00ff00);	

	a = x + 56 * sin_tab[_hour * 5 + my_minute / 12] / 10000; 
	b = y - 56 * cos_tab[_hour * 5 + my_minute / 12] / 10000;
	paint_line (x, y, a, b , 0x000000);	
	__asm__ ("sti");
}

// paint clock end

void init_exception_interrupt(void) {
	/*
	extern void divide_error(void);
	extern void single_step(void);
	extern void nmi(void);
	extern void breakpoint(void);
	extern void overflow(void);
	extern void bounds_check(void);
	extern void inval_opcode(void);
	extern void device_not_available(void);
	extern void double_fault(void);
	extern void coprocessor_segment_overrun(void);
	extern void invaild_tss(void);
	extern void segment_not_present(void);
	extern void stack_segment(void);
	extern void general_protection(void);
	extern void page_fault(void);
	extern void coprocessor_error(void);
	extern void reserved(void);
	*/	
	install_gate(0, (ui32)divide_error, 7 * 8, 0x8e00);	
	install_gate(1, (ui32)single_step, 7 * 8, 0x8e00);
	install_gate(2, (ui32)nmi, 7 * 8, 0x8e00);
	install_gate(3, (ui32)breakpoint, 7 * 8, 0x8e00);
	install_gate(4, (ui32)overflow, 7 * 8, 0x8e00);
	install_gate(5, (ui32)bounds_check, 7 * 8, 0x8e00);
	install_gate(6, (ui32)inval_opcode, 7 * 8, 0x8e00);
	install_gate(7, (ui32)device_not_available, 7 * 8, 0x8e00);
	install_gate(8, (ui32)double_fault, 7 * 8, 0x8e00);
	install_gate(9, (ui32)coprocessor_segment_overrun, 7 * 8, 0x8e00);
	install_gate(10, (ui32)invaild_tss, 7 * 8, 0x8e00);
	install_gate(11, (ui32)segment_not_present, 7 * 8, 0x8e00);
	install_gate(12, (ui32)stack_segment, 7 * 8, 0x8e00);
	install_gate(13, (ui32)general_protection, 7 * 8, 0x8e00);
	install_gate(14, (ui32)page_fault, 7 * 8, 0x8e00);
	install_gate(15, (ui32)reserved, 7 * 8, 0x8e00);
	install_gate(16, (ui32)coprocessor_error, 7 * 8, 0x8e00);

	install_gate(0x20, (ui32)clock_interrupt, 7 * 8, 0x8e00);
	install_gate(0x21, (ui32)keyboard, 7 * 8, 0x8e00);
	install_gate(0x27, (ui32)irq7_interrupt, 7 * 8, 0x8e00);
	install_gate(0x28, (ui32)rtc_interrupt, 7 * 8, 0x8e00);
	install_gate(0x2c, (ui32)mouse_interrupt, 7 * 8, 0x8e00);
}

void paint_rectangle(unsigned int x_left, unsigned int y_top, 
					unsigned int xsize, unsigned int ysize, unsigned int colour) {
	int i, j;						
	for(j = y_top; j < y_top + ysize; j++) {
		for(i = x_left; i < x_left + xsize; i++) {
			((three_byte *)(video_addr))[i + j * 1024].a[0] = colour;
			((three_byte *)(video_addr))[i + j * 1024].a[1] = colour >> 8;
			((three_byte *)(video_addr))[i + j * 1024].a[2] = colour >> 16;
		}
	}											
}

												
void paint_char(unsigned int x_left, unsigned int y_top, 
				unsigned int colour, char *font) {
	int i, j;
	char c;
	for(j = y_top; j < y_top + 16; j++) {
		c = font[j - y_top];
		for(i = x_left; i < x_left + 8; i++) {
			if(c & (0x80 >> (i - x_left))) {
				((three_byte *)(video_addr))[i + j * 1024].a[0] = colour;
				((three_byte *)(video_addr))[i + j * 1024].a[1] = colour >> 8;
				((three_byte *)(video_addr))[i + j * 1024].a[2] = colour >> 16;			
			}
		}		
	}
}					
						
void paint_str_black(unsigned int x_left, unsigned int y_top, unsigned int colour, char* str) {
	extern char myfont[4096];

	while(*str) {
		if(syspos.count == 2048) {
			syspos.count++;
			paint_char(x_left, y_top, colour, myfont + *str * 16);
			x_left += 8;			
		}
		if(syspos.count > 2048) {
			paint_rectangle(0, 512, 1024, 256, 0x000000); //0x9c9c9c
			syspos.x = 0;
			syspos.y = 512;
			syspos.count = 0;
		}
		x_left = syspos.x;
		y_top = syspos.y;
		if(*str == '\n') {
			str++;
			syspos.count = syspos.count - syspos.count % 128 + 128;
		} else {
			syspos.count++;
			paint_char(x_left, y_top, colour, myfont + *str++ * 16);
			x_left += 8;
		}
		if(!(syspos.count % 128)) {
			x_left = 0;
			y_top += 16;
		}
		syspos.x = x_left;
		syspos.y = y_top;
	}
}						


void paint_str(unsigned int x_left, unsigned int y_top, unsigned int colour, char* str) {
	extern char myfont[4096];
	while(*str) {
		paint_char(x_left, y_top, colour, myfont + *str++ * 16);
		x_left += 8;			
	}
}

void paint_point(int x, int y, unsigned int colour) {
	((three_byte *)(video_addr))[x + y * 1024].a[0] = colour;
	((three_byte *)(video_addr))[x + y * 1024].a[1] = colour >> 8;
	((three_byte *)(video_addr))[x + y * 1024].a[2] = colour >> 16; 	
}

void paint_circle(int x_center, int y_center, int r, unsigned int colour) {
	int x, y, d;
	x = 0;
	y = r;
	d = 3 - 2 * r;
	paint_point(x + x_center, y + y_center, colour);
	while(x < y) {
		if(d < 0) {
			d = d + 4 * x + 6;
		} else {
			d = d + 4 * (x - y) + 10;
			y--;
		}
		x++;
		paint_point(x + x_center, y + y_center, colour);
		paint_point(y + x_center, x + y_center, colour);
		paint_point(y + x_center, -x + y_center, colour);
		paint_point(x + x_center, -y + y_center, colour);
		paint_point(-x + x_center, -y + y_center, colour);
		paint_point(-y + x_center, -x + y_center, colour);
		paint_point(-x + x_center, y + y_center, colour);
		paint_point(-y + x_center, x + y_center, colour);
	}
	
}

void paint_line(int start_x, int start_y, int end_x, int end_y, unsigned int colour) {
	int i, x, y, len, dx, dy;
	dx = end_x - start_x;
	dy = end_y - start_y;
	x = start_x << 10;
	y = start_y << 10;
	if(dx < 0) {
		dx = -dx;
	}
	if(dy < 0) {
		dy = -dy;
	}
	if(dx >= dy) {
		len = dx + 1;
		if(start_x > end_x) {
			dx = -1024;
		} else {
			dx = 1024;
		}
		
		if(start_y <= end_y) {
			dy = ((end_y - start_y + 1) << 10) / len;
		} else {
			dy = ((end_y - start_y - 1) << 10) / len;
		}
	} else {
		len = dy + 1;
		if(start_y > end_y) {
			dy = -1024;
		} else {
			dy = 1024;
		}
		if(start_x <= end_x) {
			dx = ((end_x - start_x + 1) << 10) / len;
		} else {
			dx = ((end_x - start_x - 1) << 10) / len;			
		}
	}
	for(i = 0; i < len; i++) {
		((three_byte *)(video_addr))[(x >> 10) + (y >> 10) * 1024].a[0] = colour;
		((three_byte *)(video_addr))[(x >> 10) + (y >> 10) * 1024].a[1] = colour >> 8;
		((three_byte *)(video_addr))[(x >> 10) + (y >> 10) * 1024].a[2] = colour >> 16; 
		x += dx;
		y += dy;
	}
}	
						
unsigned int mydiv(unsigned int* i, unsigned int n) {
	unsigned int t;
	t = *i % n;
	*i /= n;
	return t;
}

unsigned int mystrlen(char* s) {
	unsigned int len = 0;
	while(*s) {
		s++;
		len++;
	}
	return len;
}

char* i2a(unsigned int i, unsigned int n) {
	static char num_const[] = "0123456789abcdef";
	static char str_temp[64];
	static char str_return[64];
	char* p = str_temp, *q = str_return;
	if(!i) {
		str_return[0] = '0';
		str_return[1] = '\0';
		return str_return;
	}
	while(i) {
		*p++ = num_const[mydiv(&i, n)];
	}
	*p = '\0';
	int l = mystrlen(str_temp), j;
	for(j = 0; j < l; j++) {
		*q++ = *--p;
	}
	*q = '\0';
	return str_return;
}

void kprintf(const char* s, ...) {
	static char str_return[1024];
	unsigned int l = mystrlen((char *)s);
	char* p = str_return, * q;
	void** args = (void**)&s;
	int i;
	args++;
	while(*s) {
		if(*s != '%') {
			*p++ = *s++;
		} else {
			s++;
			switch(*s) {
			case 's':
				s++;
				q = (char*)*args++;
				l = l + mystrlen(q) - 2;
				while(*q)  {
					*p++ = *q++;
				}
			break;
			case 'd':
				s++;
				i = (int)*args++;
				q = i2a(i, 10);
				l = l + mystrlen(q) - 2;
				while(*q)  {
					*p++ = *q++;
				}				
			break;
			case 'x':
				s++;
				i = (int)*args++;
				q = i2a(i, 16);
				l = l + mystrlen(q) - 2;
				*p++ = '0';
				*p++ = 'x';
				while(*q)  {
					*p++ = *q++;
				}
			break;
			case 'c':
				i = (int)*args++;
				*p++ = i;
			break;
			case 'b':
				s++;
				i = (int)*args++;
				q = i2a(i, 2);
				l = l + mystrlen(q) - 2;
				while(*q)  {
					*p++ = *q++;
				}
				*p++ = 'b';
			break;
			}
		}
	}
	*p = '\0';
	paint_str_black(syspos.x, syspos.y, 0xffffff, str_return);
}				
						
						
void draw_circle_point(int x0, int y0, int x, int y, unsigned int colour) {
	paint_point(x0 + x, y0 + y, colour);
	paint_point(x0 + y, y0 + x, colour);	
	paint_point(x0 - x, y0 + y, colour);	
	paint_point(x0 - y, y0 + x, colour);
	
	paint_point(x0 + x, y0 - y, colour);	
	paint_point(x0 + y, y0 - x, colour);	
	paint_point(x0 - x, y0 - y, colour);	
	paint_point(x0 - y, y0 - x, colour);		
}	



void middle_point_circle(int x0, int y0, int r, unsigned int colour) {
	int x = 0, y = r;
	int d = 1 - r;
	draw_circle_point(x0, y0, x, y, colour);
	while(x <= y) {
		if(d < 0) {
			d += 2 * x + 3;
		} else {
			d += 2 * (x - y) + 5;
			y--;
		}
		x++;
		draw_circle_point(x0, y0, x, y, colour);		
	}
}

void paint_circle0(int x0, int y0, int r, unsigned int colour) {
	int i = r;
	while(i) {
		middle_point_circle( x0,  y0, i--, colour);		
	}
}

void paint_rectangle0(int xs, int ys, int xsize, int ysize, unsigned int colour) {
	int i, j;
	for(i = xs; i < xs + xsize; i++) {
		paint_point(i, ys, colour);
	}
	for(j = ys; j < ys + ysize; j++) {
		paint_point(xs + xsize - 1, j, colour);
	}
	for(i = xs; i < xs + xsize; i++) {
		paint_point(i, ys + ysize - 1, colour);
	}
	for(j = ys; j < ys + ysize; j++) {
		paint_point(xs, j, colour);
	}
}

void fillcircle(int x0, int y0, int r, unsigned int colour) {
	int x, y;
	for(x = x0 - r; x <= x0 + r; x++) {
		for(y = y0 - r; y <= y0 + r; y++) {
			if((x - x0) * (x - x0) + (y - y0) * (y - y0) <= r * r) {
				paint_point(x, y, colour);
			}
		}
	}
}

unsigned int getcolour(int x, int y) {
	int r, g, b;
	r = ((three_byte*)video_addr)[x + y * 1024].a[0];
	g = ((three_byte*)video_addr)[x + y * 1024].a[1]; 
	b = ((three_byte*)video_addr)[x + y * 1024].a[2];
	return r + (g << 8) + (b << 16);
}

void floodfill4(int x, int y, unsigned int oldcolour, unsigned int newcolour) {
	if(getcolour(x, y) == oldcolour) {
		paint_point(x, y, newcolour);
		floodfill4(x, y - 1, oldcolour, newcolour);
		floodfill4(x, y + 1, oldcolour, newcolour);
		floodfill4(x - 1, y, oldcolour, newcolour);
		floodfill4(x + 1, y, oldcolour, newcolour);
	}
}

void buf_copy(char* s, char* d, unsigned int l) {
	char* i = s, * j = d, * k = s + l;
	while(i < k) {
		*j++ = *i++;
	}
}

ui64 create_gate(ui32 offset, ui16 selector, ui16 attrib) {
	ui64 gate, offset_low, offset_high, selector_t, attrib_t;
	offset_low = offset & 0x0000ffff;
	offset_high = offset & 0xffff0000;
	selector_t = selector;
	attrib_t = attrib;
	gate = offset_low | (offset_high << 32) | (selector_t << 16) | (attrib_t << 32);
	return gate;
}

void install_gate(ui16 num, ui32 offset, ui16 selector, ui16 attrib) {
	((ui64*)idt_start)[num] = create_gate(offset, selector, attrib);
}

void divide_error_handler(void) {
	kprintf("Divide Error!");
	while(1);
}

void single_step_handler(void) {
	kprintf("Debug Exception!");
	while(1);
}

void nmi_handler(void) {
	kprintf("NMI Exception!");
	while(1);
}

void breakpoint_handler(void) {
	kprintf("Int 3!");
	while(1);
}

void overflow_handler(void) {
	kprintf("OverFlow Exception!");
	while(1);
}

void bounds_check_handler(void) {
	kprintf("bounds_check Exception!");
	while(1);
}

void inval_opcode_handler(void) {
	kprintf("Inval Op Exception!");
	while(1);
}

void device_not_available_handler(void) {
	kprintf("Eevice not available Exception!");
	while(1);
}

void double_fault_handler(void) {
	kprintf("Double Fault Exception!");
	while(1);
}

void coprocessor_segment_overrun_handler(void) {
	kprintf("Coprocessor segment overrun Exception!");
	while(1);
}

void invaild_tss_handler(void) {
	kprintf("Invaild Tss Exception!");
	while(1);
}

void segment_not_present_handler(void) {
	kprintf("Segment not present Exception!");
	while(1);
}

void stack_segment_handler(void) {
	kprintf("Stack segment Exception!");
	while(1);
}

void general_protection_handler(ui32 ret_address, ui32 error_code) {
	kprintf("General Protection Exception!\n");
	kprintf("ret_address == %x error_code == %x\n", ret_address, error_code);
	while(1);
}

void page_fault_handler(unsigned int error_code) {
	kprintf("Page Fault Exception!  %x  ", error_code);
	while(1);
}

void coprocessor_error_handler(void) {
	kprintf("Coprocessor Error Exception!");
	while(1);
}

void reserved_handler(void) {
	kprintf("Reserved! Exception!");
	while(1);
}


void init_8259(void) {
	out(0x21, 0xff);
	out(0xa1, 0xff);
	
	out(0x20, 0x11);
	out(0x21, 0x20);	
	out(0x21, 0x04);
	out(0x21, 0x01);
	
	out(0xa0, 0x11);
	out(0xa1, 0x28);
	out(0xa1, 0x02);
	out(0xa1, 0x01);
	
	out(0x21, 0xff);
	out(0xa1, 0xff);
}

void init_rtc(void) {
	out(0x70, 0x8b);
	out(0x71, 0x12);
	out(0x70, 0xc);
	in(0x71);
}

void rtc_handler(void) {
	__asm__ __volatile("cli");
	system_count++;
	out(0x70, 4);
	crt_data.hour = in(0x71);
	out(0x70, 2);
	crt_data.minute = in(0x71);
	out(0x70, 0);
	crt_data.second = in(0x71);
	out(0x70, 0xc);	
	in(0x71);
	fifo32_put(&_fifo, 0xffff);
	__asm__ __volatile__("sti");
}

void irq7_interrupt_handler(void) {
	kprintf("@@@IRQ7@@@ is so crasy! but not known hanpend how times.");	
}

void keyboard_handler(void) {
	ui32 c = in(0x60);
//	fifo32_put(&_fifo, (c & 0xff) + 256);

	if(!ioq_full(&kbd_buf)) {
		ioq_putchar(&kbd_buf, c);
	}

	out(0x20, 0x61);
}

void init_8253(void) {
	#define frequency 1193182
	#define hz 100
	#define temp frequency / hz
	out(0x43, 0x34);
	out(0x40, temp & 0xff);
	out(0x40, temp >> 8);
}

ui64 create_descriptor(ui32 base, ui32 limit, ui16 attrib) {
	ui64 descriptor, base_low24, base_high8, limit_low16, limit_high4, attrib_t;
	base_low24 = 0x00ffffff & base;
	base_high8 = 0xff000000 & base;
	limit_low16 = 0x0000ffff & limit;
	limit_high4 = 0x000f0000 & limit;
	descriptor = base_low24 << 16 | base_high8 << 32 | limit_low16 | limit_high4 << 32 | attrib_t << 40 ;
	return descriptor;
}




void wait_kbc_sendready(void) {
	while((in(0x64) & 0x02));
}

void init_keyboard(void) {
	wait_kbc_sendready();
	out(0x64, 0x60);
	wait_kbc_sendready();
	out(0x60, 0x47);
}

void enable_mouse(void) {
	wait_kbc_sendready();
	out(0x64, 0xd4);
	wait_kbc_sendready();
	out(0x60, 0xf4);
}

void mouse_interrupt_handler(void) {
	ui32 c = in(0x60);
//	fifo32_put(&_fifo, (c & 0xff) + 512);
	
	out(0xa0, 0x64);
	out(0x20, 0x62);
}


void* test(void) {
	static struct mem_elem e;
	return &e;
}


// memory manager start. @2


// memory manager end. @2

// eflags start.

bool __cli(void) {
	unsigned int old_status;
	__asm__ volatile ("pushf; pop %0":"=a"(old_status));
	if(old_status & _IF_BIT) {
		cli();
		return true;
	}
	return false;
}

bool __sti(void) {
	unsigned int old_status;
	__asm__ volatile ("pushf; pop %0":"=a"(old_status));
	if(!(old_status & _IF_BIT)) {
		sti();
		return false;
	}
	return true;	
}

// eflags end.

// assert and panic start.
		
void _panic(const char* basefile, const char* filename,
			const char* func, unsigned int line, 
			const char* exp) {
	__cli();
	kprintf("\nBase File = %s  |  File Name = %s\n",
	basefile, filename);
	kprintf("Function = %s  |  Expression = %s\n",
	func, exp);
	kprintf("Line = %d\n ", line);
	for(;;);
}

// assert and panic end.

// string start.

void mem_set(void* d, unsigned char value, unsigned int size) {
	_assert(d);
	int i;
	for(i = 0; i < size; i++) {
		((char*)d)[i] = value;
	}
}

void mem_copy(void * d, void* s, unsigned int size) {
	_assert(d && s);
	int i;
	for(i = 0; i < size; i++) {
		((char*)d)[i] = ((char*)s)[i];
	}
}

// string end.

// bitmap start.

void init_bit_map(struct bit_map* map) {
	mem_set(map->start, 0, map->byte_size);
}

bool bit_check(struct bit_map* map, unsigned int bit_index) {
	if(map->start[bit_index / 8] & (1 << (bit_index % 8))) {
		return true;
	} else {
		return false;
	}
}

void bit_set(struct bit_map* map, unsigned char value, unsigned int bit_index) {
	_assert((value == 0) || (value == 1));
	unsigned int byte_index = bit_index / 8;
	unsigned char offset_in_byte = bit_index % 8;
	if(value) {
		map->start[byte_index] |= (1 << offset_in_byte);
	} else {
		map->start[byte_index] &= ~(1 << offset_in_byte);
	}
}

unsigned int find_counts_zero_bit(struct bit_map* map, unsigned int bit_counts) {
	signed int bit_start = 0;
	while(bit_check(map, bit_start) && (bit_start < (map->byte_size * 8))) {		
		bit_start++;
	}
	
	if(bit_start >= (map->byte_size * 8)) {
		return -1;
	}

	if(bit_counts == 1) {
		return bit_start;
	}
	
	unsigned c = 1, free_bits_t = map->byte_size * 8 - bit_start;
	signed int bit_start_t = bit_start + 1;
	
	bit_start = -1;
	while(free_bits_t > 0) {
		if(!bit_check(map, bit_start_t)) {
			c++;
		} else {
			c = 0;
		}
		if(c >= bit_counts) {
			bit_start = bit_start_t - bit_counts + 1;
			return bit_start;
		}
		bit_start_t++;
		free_bits_t--;
	}
	return bit_start;
}

// bitmap end.

// first in first out start.

/*
struct fifo32 {
	int next_w, next_r, size, free, flags;
	unsigned int* buf;
};
*/

void init_fifo32(struct fifo32* fifo, int size,
				unsigned int* buf) {
	fifo->next_w = 0;
	fifo->next_r = 0;
	fifo->size = size;
	fifo->free = size;
	fifo->flags = 0;
	fifo->buf = buf;
}

int fifo32_put(struct fifo32* fifo, unsigned int data) {
	if(fifo->free == 0) {
		fifo->flags = 1;
		return -1;
	}
	fifo->buf[fifo->next_w++] = data;
	if(fifo->next_w == fifo->size) {
		fifo->next_w = 0;
	}
	fifo->free--;
	return 0;
}

unsigned int fifo32_get(struct fifo32* fifo) {
	unsigned int data;
	if(fifo->free == fifo->size) {
		return -1;
	}
	data = fifo->buf[fifo->next_r++];
	if(fifo->next_r == fifo->size) {
		fifo->next_r = 0;
	}
	fifo->free++;
	return data;
}

int fifo32_status(struct fifo32* fifo) {
	return fifo->size - fifo->free;
}

// first in first out end.


// old string, bitmap, memory manager start.

void _memset(void* d, unsigned char value, unsigned int size) {
	_assert(d);
	int i;
	for(i = 0; i < size; i++) {
		((unsigned char*)d)[i] = value;
	}
}

void _memcpy(void* d, void* s, unsigned int size) {
	_assert(d && s);
	int i;
	for(i = 0; i < size; i++) {
		((unsigned char*)d)[i] = ((unsigned char*)s)[i];
	}
}


void bitmap_init(struct bitmap* btmp) {
	_memset(btmp->bits, 0, btmp->btmp_bytes_len);
}

bool bitmap_scan_test(struct bitmap* btmp, unsigned int bit_idx) {
	unsigned int byte_idx = bit_idx / 8; // bit_idx >> 3
	unsigned int bit_odd = bit_idx % 8; // bit_idx & 0x00000007
	return (btmp->bits[byte_idx] & (1 << bit_odd));
}

int bitmap_scan(struct bitmap* btmp, unsigned int cnt) {
	unsigned int idx_byte = 0;
	while((0xff == btmp->bits[idx_byte]) && (idx_byte < btmp->btmp_bytes_len)) {
		idx_byte++;
	}
	_assert(idx_byte < btmp->btmp_bytes_len);
	if(idx_byte >= btmp->btmp_bytes_len) {
		return -1;
	}
	unsigned int idx_bit = 0;
	while((unsigned char)(1 << idx_bit) & btmp->bits[idx_byte]) {
		idx_bit++;
	}
	int bit_idx_start = idx_byte * 8 + idx_bit;
	if(cnt == 1) {
		return bit_idx_start;
	}
	
	unsigned int bit_left = btmp->btmp_bytes_len * 8 - bit_idx_start;
	unsigned int next_bit = bit_idx_start + 1;
	unsigned int count = 1;
	
	bit_idx_start = 1;
	while(bit_left-- > 0) {
		if(!bitmap_scan_test(btmp, next_bit)) {
			count++;
		} else {
			count = 0;
		}
		if(count >= cnt) {
			bit_idx_start = next_bit - cnt + 1;
			break;
		}
		next_bit++;
	}
	return bit_idx_start;
}

void bitmap_set(struct bitmap* btmp, unsigned int bit_idx, signed char value) {
	_assert((value == 0) || (value == 1));
	unsigned int byte_idx = bit_idx / 8;
	unsigned int bit_odd = bit_idx % 8;
	if(value) {
		btmp->bits[byte_idx] |= (1 << bit_odd);
	} else {
		btmp->bits[byte_idx] &= ~(1 << bit_odd);
	}
}


// memory start.



struct virtual_addr kernel_vaddr;
struct pool kernel_pool, user_pool;

static void mem_pool_init(unsigned int all_mem) {
	kprintf(" mem_pool_init start\n");
	unsigned int page_table_size = 4096 * 1024;
	unsigned int used_mem = page_table_size + 0x400000;
	
	unsigned int free_mem = all_mem - used_mem;
	unsigned int all_free_pages = free_mem / 4096;
	
	unsigned int kernel_free_pages = all_free_pages / 2;
	unsigned int user_free_pages = all_free_pages - kernel_free_pages;
	
	unsigned int kbm_length = kernel_free_pages / 8;
	unsigned int ubm_length = user_free_pages / 8;
	
	unsigned int kp_start = 0x400000;
	unsigned int up_start = kp_start + kernel_free_pages * 4096;
	
	kernel_pool.phy_addr_start = kp_start;
	user_pool.phy_addr_start = up_start;
	
	kernel_pool.pool_size = kernel_free_pages * 4096;
	user_pool.pool_size = user_free_pages * 4096;
	
	kernel_pool.pool_bitmap.btmp_bytes_len = kbm_length;
	user_pool.pool_bitmap.btmp_bytes_len = ubm_length;
	
	kernel_pool.pool_bitmap.bits = (void*) 0x300000;
	user_pool.pool_bitmap.bits = (void*)(0x300000 + kbm_length);
	
	kprintf("  kernel_pool_bitmap_start:%x", kernel_pool.pool_bitmap.bits);
	kprintf("  kernel_pool_phy_addr_start:%x\n", kernel_pool.phy_addr_start);
	kprintf("  kernel_pool.pool_size:%x", kernel_pool.pool_size);
	kprintf("  user_pool.pool_size:%x\n", user_pool.pool_size);	
	kprintf("  user_pool_bitmap_start:%x", user_pool.pool_bitmap.bits);
	kprintf("  user_pool_phy_addr_start:%x\n", user_pool.phy_addr_start);
	kprintf("  free_mem:%x\n", free_mem);
	

	
	bitmap_init(&kernel_pool.pool_bitmap);
	bitmap_init(&user_pool.pool_bitmap);
	
	kernel_vaddr.vaddr_bitmap.btmp_bytes_len = kbm_length;
	
	kernel_vaddr.vaddr_bitmap.bits = 
		(void*) (0x300000 + kbm_length + ubm_length);

	kernel_vaddr.vaddr_start = 0x80000000 + 0x400000;
	bitmap_init(&kernel_vaddr.vaddr_bitmap);
	
	kprintf(" mem_pool_init_done\n");
}


void mem_init(void) {
	kprintf("mem_init start\n");
	unsigned int mem_bytes_total = 512 * 1024 * 1024;
	mem_pool_init(mem_bytes_total);
	kprintf("mem_init done\n");
}

// memory end.

// memory part 2 start.

unsigned int* pte_ptr(unsigned int vaddr) {
	unsigned int* pte = (unsigned int*)(0x00400000 + ((vaddr & 0xffc00000) >> 10)
					+ PTE_IDX(vaddr) * 4);
	return pte;
}

unsigned int* pde_ptr(unsigned int vaddr) {
	unsigned int* pde = (unsigned int*)(0x00401000 + PDE_IDX(vaddr) * 4);
	return pde;
}

unsigned int* pte_ptr1(unsigned int vaddr) {
	unsigned int* pte = (unsigned int*)(0xffc00000 + ((vaddr & 0xffc00000) >> 10)
					+ PTE_IDX(vaddr) * 4);
	return pte;
}

unsigned int* pde_ptr1(unsigned int vaddr) {
	unsigned int* pde = (unsigned int*)(0xfffff000 + PDE_IDX(vaddr) * 4);
	return pde;
}


static void* vaddr_get(enum pool_flags pf, unsigned int pg_cnt) {
	int vaddr_start = 0, bit_idx_start = -1;
	unsigned int cnt = 0;
	if(pf = PF_KERNEL) {
		bit_idx_start = bitmap_scan(&kernel_vaddr.vaddr_bitmap, pg_cnt);
		if(bit_idx_start == -1) {
			return NULL;
		}
		while(cnt < pg_cnt) {
			bitmap_set(&kernel_vaddr.vaddr_bitmap,
						bit_idx_start + cnt++, 1);
		}
		vaddr_start = kernel_vaddr.vaddr_start +
					  bit_idx_start * 4096;
	} else {
		
	}
	return (void*)vaddr_start;
}

static void* palloc(struct pool* m_pool) {
	int bit_idx = bitmap_scan(&m_pool->pool_bitmap, 1);
	if(bit_idx == -1) {
		return NULL;
	}
	bitmap_set(&m_pool->pool_bitmap, bit_idx, 1);
	unsigned page_phyaddr = (bit_idx * 4096)
							+ m_pool->phy_addr_start;
	return (void*) page_phyaddr;
}


static void page_table_add(void* _vaddr, void* _page_phyaddr) {
	unsigned int vaddr = (unsigned int) _vaddr;
	unsigned int page_phyaddr = (unsigned int) _page_phyaddr;
	unsigned int* pde = pde_ptr(vaddr);
	unsigned int* pte = pte_ptr(vaddr);
	
	if(*pde & 0x00000001) {
		_assert(!(*pte & 0x00000001));
		if(!(*pte & 0x00000001)) {
			*pte = page_phyaddr | 7;
		} else {
			
		}
	} else {
		unsigned int pde_phyaddr = (unsigned int)palloc(&kernel_pool);
		*pde = pde_phyaddr | 7;
		_memset((void*)((int)pte & 0xfffff000), 0, 4096);
		_assert(!(*pte & 0x00000001));
		*pte = page_phyaddr | 7;
	}
}

void* malloc_page(enum pool_flags pf, unsigned int pg_cnt) {
	_assert(pg_cnt > 0);
	void* vaddr_start = vaddr_get(pf, pg_cnt);
	if(vaddr_start == NULL) {
		return NULL;
	}
	unsigned int vaddr = (unsigned int) vaddr_start, cnt = pg_cnt;
	struct pool* mem_pool = 
			 pf & PF_KERNEL ? &kernel_pool : &user_pool;
	while(cnt-- > 0) {
		void* page_phyaddr = palloc(mem_pool);
		if(page_phyaddr == NULL) {
			return NULL;
		}
		page_table_add((void*)vaddr, page_phyaddr);
		vaddr += 4096;
	}
	return vaddr_start;
}

void* get_kernel_pages(unsigned int pg_cnt) {
	void* vaddr = malloc_page(PF_KERNEL, pg_cnt);
	if(vaddr != NULL) {
		_memset(vaddr, 0, pg_cnt * 4096);
	}
	return vaddr;
}

// memory part 2 end.

// old string, bitmap, memory manager end.


// list start.

void list_init(struct list* list) {
	list->head.prev = NULL;
	list->head.next = &list->tail;
	list->tail.prev = &list->head;
	list->tail.next = NULL;
}

void list_insert_before(struct list_elem* before, struct list_elem* elem) {
	enum intr_status old_status = intr_disable();
	before->prev->next = elem;
	elem->prev = before->prev;
	elem->next = before;
	before->prev = elem;
	intr_set_status(old_status);
}

void list_push(struct list* plist, struct list_elem* elem) {
	list_insert_before(plist->head.next, elem);
}

void list_append(struct list* plist, struct list_elem* elem) {
	list_insert_before(&plist->tail, elem);
}

void list_remove(struct list_elem* pelem) {
	enum intr_status old_status = intr_disable();
	pelem->prev->next = pelem->next;
	pelem->next->prev = pelem->prev;
	intr_set_status(old_status);
}

struct list_elem* list_pop(struct list* plist) {
	struct list_elem* elem = plist->head.next;
	list_remove(elem);
	return elem;
}

bool elem_find(struct list* plist, struct list_elem* obj_elem) {
	struct list_elem* elem = plist->head.next;
	while(elem != &plist->tail) {
		if(elem == obj_elem) {
			return true;
		}
		elem = elem->next;
	}
	return false;
}

struct list_elem* list_traversal(struct list* plist, function func, int arg) {
	struct list_elem* elem = plist->head.next;
	if(list_empty(plist)) {
		return NULL;
	}
	while(elem != &plist->tail) {
		if(func(elem, arg)) {
			return elem;
		}
		elem = elem->next;
	}
	return NULL;
}

unsigned int list_len(struct list* plist) {
	struct list_elem* elem = plist->head.next;
	unsigned int length = 0;
	while(elem != &plist->tail) {
		length++;
		elem = elem->next;
	}
	return length;
}

bool list_empty(struct list* plist) {
	return (plist->head.next == &plist->tail ? true : false);
}

// list end.





struct task_struct* running_thread(void) {
	unsigned int esp;
	__asm__ volatile ("mov %0, esp":"=g"(esp));
	return (struct task_struct*)(esp & 0xfffff000);
}

static void kernel_thread(thread_func* function, void* func_arg) {
	__sti();
	intr_enable();
	function(func_arg);
}

void thread_create(struct task_struct* pthread, thread_func function, void* func_arg) {
	pthread->self_kstack -= sizeof(struct intr_stack);
	pthread->self_kstack -= sizeof(struct thread_stack);
	struct thread_stack* kthread_stack = (struct thread_stack*)
						pthread->self_kstack;
	kthread_stack->eip = kernel_thread;
	kthread_stack->function = function;
	kthread_stack->func_arg = func_arg;
	kthread_stack->edi = kthread_stack->esi = kthread_stack->ebp =
	kthread_stack->ebx = 0; 
/*	
	kthread_stack->edi = kthread_stack->esi = kthread_stack->ebp =
	kthread_stack->esp = kthread_stack->ebx = kthread_stack->edx = 
	kthread_stack->ecx = kthread_stack->eax = 0; 
*/
}

void init_thread(struct task_struct* pthread, char* name, int proi) {
	_memset(pthread, 0, sizeof(*pthread));
	_strcpy(pthread->name, name);
	if(pthread == main_thread) {
		pthread->status = TASK_RUNNING;
	} else {
		pthread->status = TASK_READY;
	}
	pthread->self_kstack = (unsigned int*) ((unsigned int)pthread + 4096);
	pthread->priority = proi;
	pthread->ticks = proi;
	pthread->elapsed_ticks = 0;
	pthread->pgdir = NULL;
	pthread->stack_magic = 20211118;
}

struct task_struct* thread_start(char* name,
								int proi,
								thread_func function,
								void* func_arg) {
	struct task_struct* thread = get_kernel_pages(1);
	init_thread(thread, name, proi);
	thread_create(thread, function, func_arg);
	
	_assert(!elem_find(&thread_ready_list, &thread->general_tag));
	list_append(&thread_ready_list, &thread->general_tag);
	
	_assert(!elem_find(&thread_all_list, &thread->all_list_tag));
	list_append(&thread_all_list, &thread->all_list_tag);
	
	return thread;
}

static void make_main_thread(void) {
	main_thread = running_thread();
	init_thread(main_thread, "main", 31);
	_assert(!elem_find(&thread_all_list, &main_thread->all_list_tag));
	list_append(&thread_all_list, &main_thread->all_list_tag);
}


void intr_timer_handler(void) {
	struct task_struct* cur_thread = running_thread();
	_assert(cur_thread->stack_magic == 20211118);
	cur_thread->elapsed_ticks++;
	ticks++;	
	if(cur_thread->ticks == 0) {
		schedule();
	} else {
		cur_thread->ticks--;
	}
}

void schedule(void) {
	_assert(intr_get_status() == INTR_OFF);
	

	
	struct task_struct* cur = running_thread();
	if(cur->status == TASK_RUNNING) {
		_assert(!elem_find(&thread_ready_list, &cur->general_tag));
		list_append(&thread_ready_list, &cur->general_tag);
		cur->ticks = cur->priority;
		cur->status = TASK_READY;
	} else {
		
	}
	_assert(!list_empty(&thread_ready_list));
	thread_tag = NULL;
	thread_tag = list_pop(&thread_ready_list);
	struct task_struct* next = elem2entry(struct task_struct, 
								general_tag, thread_tag);
	next->status = TASK_RUNNING;
//		while(1) {
//			kprintf(" %d ", list_len(&thread_ready_list));
//		}
	switch_to(cur, next);
	
}

// interrupt status start.


enum intr_status intr_enable(void) {
	enum intr_status old_status;
	if(INTR_ON == intr_get_status()) {
		old_status = INTR_ON;
		return old_status;
	} else {
		old_status = INTR_OFF;
		__asm__ volatile("sti");
		return old_status;
	}
}

enum intr_status intr_disable(void) {
	enum intr_status old_status;
	if(INTR_ON == intr_get_status()) {
		old_status = INTR_ON;
		__asm__ volatile("cli":::"memory");
		return old_status;
	} else {
		old_status = INTR_OFF;
		return old_status;
	}
}

enum intr_status intr_set_status(enum intr_status status) {
	return status & INTR_ON ? intr_enable() : intr_disable();
}

enum intr_status intr_get_status(void) {
	unsigned int eflags = 0;
	GET_EFLAGS(eflags);
	return (EFLAGS_IF & eflags) ? INTR_ON : INTR_OFF; 
}


// interrupt status end.


// string 2 start.

void _strcpy(char* d, char* s) {
	_assert(d);
	while(*s) {
		*d++ = *s++;
	}
}

// string 2 end.


// thread 2 start.

void thread_init(void) {
	kprintf("thread init start\n");
	list_init(&thread_ready_list);
	list_init(&thread_all_list);
	make_main_thread();
	kprintf("thread init done\n");
}


void k_thread_a(void* arg) {
	char* para = arg;
	create_clock(200, 200);
	while(1) {
		__cli();
			lock_clock();
		__sti();
	}
}


void k_thread_b(void* arg) {
	char* para = arg;
	create_clock(600, 200);	
	while(1) {
		__cli();
			lock_clock1();		
		__sti();
	}
}



// thread 2 end.


// ipc start.

void thread_block(enum task_status stat) {
	_assert(((stat == TASK_BLOCKED) || (stat == TASK_WAITING)
			|| (stat == TASK_HANGING)));
	enum intr_status old_status = intr_disable();
	struct task_struct* cur_thread = running_thread();
	cur_thread->status = stat;
	schedule();
	intr_set_status(old_status);
}

void thread_unblock(struct task_struct* pthread) {
	enum intr_status old_status = intr_disable();
	_assert(((pthread->status == TASK_BLOCKED) || 
			(pthread->status == TASK_WAITING) || 
			(pthread->status == TASK_HANGING)));
	if(pthread->status != TASK_READY) {
		_assert(!elem_find(&thread_ready_list, &pthread->general_tag));
		if(elem_find(&thread_ready_list, &pthread->general_tag)) {
			kprintf("thread unblock!");
			__cli();
		}
		list_push(&thread_ready_list, &pthread->general_tag);
	}
	intr_set_status(old_status);
}

// sync start.

void sema_init(struct semaphore* psema, unsigned char value) {
	psema->value = value;
	list_init(&psema->waiters);
}

void lock_init(struct lock* plock) {
	plock->holder = NULL;
	plock->holder_repeat_nr = 0;
	sema_init(&plock->semaphore, 1);
}


void sema_down(struct semaphore* psema) {
	enum intr_status old_status = intr_disable();
	while(psema->value == 0) {
		_assert(!elem_find(&psema->waiters, &running_thread()->general_tag));
		if(elem_find(&psema->waiters, &running_thread()->general_tag)) {
			kprintf("thread has been in waiters list.");
			__cli();
		}
		list_append(&psema->waiters, &running_thread()->general_tag);
		thread_block(TASK_BLOCKED);
	}
	psema->value--;
	_assert(psema->value == 0);
	intr_set_status(old_status);
}

void sema_up(struct semaphore* psema) {
	enum intr_status old_status = intr_disable();
	_assert(psema->value == 0);
	if(!list_empty(&psema->waiters)) {
		struct task_struct* thread_blocked = elem2entry(struct task_struct,
					general_tag, list_pop(&psema->waiters));
		thread_unblock(thread_blocked);
	}
	psema->value++;
	_assert(psema->value == 1);
	intr_set_status(old_status);
}

void lock_acquire(struct lock* plock) {
	if(plock->holder != running_thread()) {
		sema_down(&plock->semaphore);
		plock->holder = running_thread();
		_assert(plock->holder_repeat_nr == 0);
		plock->holder_repeat_nr = 1;
	} else {
		plock->holder_repeat_nr++;
	}
}

void lock_release(struct lock* plock) {
	_assert(plock->holder == running_thread());
	if(plock->holder_repeat_nr > 1) {
		plock->holder_repeat_nr--;
		return;
	}
	_assert(plock->holder_repeat_nr == 1);
	plock->holder = NULL;
	plock->holder_repeat_nr = 0;
	sema_up(&plock->semaphore);
}


void console_init(void) {
	lock_init(&console_lock);
}

void console_acquire(void) {
	lock_acquire(&console_lock);
}

void console_release(void) {
	lock_release(&console_lock);
}

void console_put_str(char* s) {
	console_acquire();
	kprintf("%s", s);
	console_release();
}


void console_put_char(unsigned char c) {
	console_acquire();
	kprintf("%c", c);
	console_release();
}

void console_put_int(unsigned int i) {
	console_acquire();
	kprintf("%x", i);
	console_release();
}

void lock_clock(void) {
	console_acquire();
	paint_clock(200, 200);
	console_release();	
}


void lock_clock1(void) {
	console_acquire();
	paint_clock(600, 200);
	console_release();	
}

// sync end.

// ipc end.

// ioqueue start.



void ioqueue_init(struct ioqueue* ioq) {
	lock_init(&ioq->lock);
	ioq->producer = ioq->consumer = NULL;
	ioq->head = ioq->tail = 0;
};

static unsigned int next_pos(unsigned int pos) {
	return (pos + 1) % 64;
}

bool ioq_full(struct ioqueue* ioq) {
	_assert(intr_get_status() == INTR_OFF);
	return next_pos(ioq->head) == ioq->tail;
}

static bool ioq_empty(struct ioqueue* ioq) {
	_assert(intr_get_status() == INTR_OFF);
	return ioq->head == ioq->tail;
}

static void ioq_wait(struct task_struct** waiter) {
	_assert(*waiter == NULL && waiter != NULL);
	*waiter = running_thread();
	thread_block(TASK_BLOCKED);
}

static void wakeup(struct task_struct** waiter) {
	_assert(*waiter != NULL);
	thread_unblock(*waiter);
	*waiter = NULL;
}

char ioq_getchar(struct ioqueue* ioq) {
//	_assert(intr_get_status == INTR_OFF);
	while(ioq_empty(ioq)) {
		lock_acquire(&ioq->lock);
		ioq_wait(&ioq->consumer);
		lock_release(&ioq->lock);
	}
	char byte = ioq->buf[ioq->tail];
	ioq->tail = next_pos(ioq->tail);
	
	if(ioq->producer != NULL) {
		wakeup(&ioq->producer);
	}
	return byte;
}

void ioq_putchar(struct ioqueue* ioq, char byte) {
	_assert(intr_get_status() == INTR_OFF);
	while(ioq_full(ioq)) {
		lock_acquire(&ioq->lock);
		ioq_wait(&ioq->producer);
		lock_release(&ioq->lock);
	}
	
	ioq->buf[ioq->head] = byte;
	ioq->head = next_pos(ioq->head);
	
	if(ioq->consumer != NULL) {
		wakeup(&ioq->consumer);
	}
}





// ioqueue end.