บวกเลข 128 บิต

เมื่อวานหลังจากสอนวิชา comp arch ซึ่งกำลังพูดถึงเรื่อง computer arithmetic ก็มีนักศึกษา (ที่ยังไม่ได้ถามว่าเจ้าตัวอยากจะให้ออกนามหรือเปล่า) สงสัยว่า ถ้าเราต้องการบวกเลขที่มีขนาดใหญ่กว่า 64 บิต ซึ่งเป็นขนาดที่คอมพิวเตอร์ปัจจุบันรองรับ จะทำย้งไง หลังจากอธิบายไปจนคิดว่าคนถามน่าจะเข้าใจแล้ว ก็เกิดอาการคันไม้คันมือเล็กน้อย เลยลองเขียนฟังก์ชันบวกเลขขนาด 128 บิต
ฟังก์ชันนี้ทำงานง่ายๆ คือ เก็บข้อมูลจำนวนเต็มขนาด 128 บิต โดยใช้ข้อมูลจำนวนเต็มขนาด 64 บิต 2 ตัวต่อกัน (เรียกเป็นครึ่งบน กับครึ่งล่างละกัน) เวลาจะบวกกัน ก็แค่ เอาครึ่งล่างบวกกัน เอาครึ่งบนบวกกัน แล้วถ้ามีทดจากครึ่งล่างก็ให้เอาไปบวกเพิ่มที่ครึ่งบนด้วย แค่นี้แหละ

#include <stdio.h>
#include <stdint.h>

typedef struct {
    int64_t hi;
    int64_t lo;
} int128_t;

int128_t add128(int128_t x, int128_t y) {
    int128_t z = {0,0};
    
    z.hi = x.hi + y.hi;
    z.lo = x.lo + y.lo;
    if (z.lo < x.lo) {
        z.hi++;
    }
    
    return z;
}

int main(int argc, const char * argv[])
{
    int128_t a = {0x0000000000000001, 0xffffffffffffffff};
    int128_t b = {0x0000000000000000, 0x0000000000000005};
    int128_t c;
    
    c = add128(a, b);
    
    printf("0x%016llx %016llx", c.hi, c.lo);
    
    return 0;
}

จากโปรแกรมนี้ จะได้ c = a+b โดยที่ทั้งหมดเป็นจำนวนเต็มขนาด 128 บิต ซึ่งเก็บในลักษณะ struct ประกอบด้วย hi กับ lo เป็นจำนวนเต็มขนาด 64 บิตทั้งคู่

จุดสำคัญของฟังก์ชันนี้ คือ การทดสอบว่าเกิดการทดเลขจากครึ่งล่างหรือไม่ โดยปกติ processor จะมี carry flag เอาไว้สำหรับเก็บค่าตัวทดหลังจากการบวกเลข แต่ภาษา C มีจุดอ่อนที่ไม่สามารถเรียกใช้ค่า carry flag ได้โดยตรง ถ้าจะทำแบบนั้นก็ต้องเขียน assembly ซึ่งดูไม่สะดวก ผมจึงใช้วิธีการตรวจสอบว่าเกิด overflow ขึ้นในการบวกเลขครึ่งล่างหรือไม่ ถ้าเกิด overflow ก็แสดงว่าจะต้องทดเลข หรือบวก 1 เข้าไปที่ผลบวกของครึ่งบน ตามลิงก์นี้ และต้องขอบคุณ @cutiening ที่ช่วยแสดงวิธี prove ว่า เมื่อ a+b แล้วเกิด overflow จะได้ว่าผลที่ได้ c < a และ c < b เสมอ ก็เลยได้ if statement ตามโปรแกรม เป็นอันเสร็จสิ้นการละเล่นแต่เพียงเท่านี้

ที่นี้บวกเลข 128 บิตได้แล้ว แต่ละแสดงผลลัพธ์ออกมาเป็นเลขฐานสิบได้ยังไง ก็ต้องเป็นคำถามต่อไป

[C] แบ่งข้อความด้วย strtok

ฟังก์ชัน strtok เป็นฟังก์ชันใน standard C library ใช้สำหรับแบ่ง string ออกเป็นส่วนๆ ตามเครื่องหมาย (delimiter) ที่กำหนด รูปแบบการใช้งานก็เป็น

char *strtok(char *str, const char *delim);


str คือ string ที่ต้องการแบ่งเป็นหลายส่วน และ delim คือ string ของตัวแบ่ง (delimiter) ที่จะใช้แบ่ง string จะเห็นว่า type ของ str กำหนดเป็น char * เนื่องจากฟังก์ชัน strtok จะแก้ไข str เปลี่ยน delim ให้กลายเป็น null character เพื่อแบ่ง string

เมื่อมีการเรียกใช้งานฟังก์ชัน strtok แต่ละครั้ง ฟังก์ชันจะให้ string ที่แบ่งได้ 1 อัน โดยเริ่มจาก str ที่กำหนด ถ้าไม่สามารถแบ่งได้แล้ว เช่น เจอ null character ซะก่อน ก็จะให้ค่าเป็น ์๊NULL ถ้าข้อความที่ต้องการจะแบ่ง ประกอบด้วย token หลายๆ อัน เราจะต้องเรียก strtok หลายๆ ครั้ง แต่ครั้งที่สองเป็นต้นไป จะต้องกำหนดให้ str เป็น NULL เพื่อให้ strtok แบ่งต่อจากครั้งก่อน มิฉะนั้นมันจะเริ่มตั้งแต่ต้นใหม่

#include<stdio.h>
#include<string.h>

int main() {
char str[] = "5022771234,50,60,30";
char delim[] = ",";
char *token;

token = strtok(str, delim);
while(token != NULL) {
printf("Token: %s\n", token);
token = strtok(NULL, delim);
}

return 0;
}


จะได้ผลคือ

Token: 5022771234
Token: 50
Token: 60
Token: 30

ข้อควรระวัง strtok จะเปลี่ยนแปลง string ที่นำไปแบ่ง จนมีค่าไม่เหมือนเดิม เพราะตัวแบ่งจะถูกแทนที่ด้วย null character จนหมด ถ้าจำเป็นจะต้องเอา string นี้ไปใช้งานอื่นอีก ควรจะเก็บไว้เองก่อน

[C] จัดการ Source code หลายไฟล์ ตอนที่ 3

วันนี้มาเล่าต่อว่า จะทำยังไง ถ้าต้องการแลกเปลี่ยนข้อมูลระหว่างโปรแกรมที่เขียนแยกไว้หลายๆ ไฟล์ หรือต้องการมีตัวแปรแบบ global ที่สามารถเรียกค่าของตัวแปรจากฟังก์ชันหลายๆ ฟังก์ชันที่อยู่คนละไฟล์

ภาษา C ยอมให้ประกาศตัวแปรแบบ global โดยใช้ keyword "extern" เพื่อระบุว่ามีตัวแปรนี้อยู่แล้ว เพียงแต่อ้างถึงตัวแปรตัวเดียวกันนี้ที่ถูกประกาศไว้ที่อื่น ลองดูตัวอย่างโปรแกรมข้างล่างนี้

/* foo.c */
#include<stdio.h>
void func();
int i = 10;
main() {
 printf("i = %d\n", i);
 func();
 return 0;
}

/* bar.c */
#include<stdio.h>

extern int i;

void func() {
 printf("i = %d\n", i);
}

เมื่อคอมไพล์โปรแกรมนี้ gcc foo.c bar.c จะได้ผลเป็น

i = 10
i = 10

เพราะตัวแปร i ที่อ้างถึงทั้งในฟังก์ชัน main และ func เป็นตัวแปรเดียวกัน จึงแสดงค่า เท่ากับ 10 เหมือนกันทั้งสองบรรทัด มีข้อกำหนดเกี่ยวกับตัวแปร extern อีกเล็กน้อย คือ ตัวแปรที่ประกาศเป็น extern จะไม่สามารถกำหนดค่าเริ่มต้นให้ได้ เนื่องจากตัวแปรนั้นไม่ใช่ตัวแปรจริง เป็นแค่การอ้างถึงตัวแปรที่ประกาศไว้ที่อื่น

นอกจากนี้ถ้าประกาศตัวแปรแบบ extern นี้ไว้คนละไฟล์ โดยระบุ type ไม่เหมือนกัน คอมไพเลอร์จะไม่สามารถตรวจสอบ type ของตัวแปรว่าตรงกันได้ อาจจะทำให้การทำงานเพี้ยนไปได้ ซึ่งเป็นสิ่งที่ต้องระวัง ทางที่ดีเราจึงควรจะกำหนดตัวแปรแบบ extern ไว้ใน header file แล้วใช้แบบเดียวกันไปทุกที่

[C] จัดการ Source code หลายไฟล์ ตอนที่ 2

ต่อจากตอนที่แล้ว ต้นเหตุที่ทำให้ได้ผลไม่ถูก ก็คือการไม่กำหนด function prototype ถ้าคอมไพล์โปรแกรมนี้ใหม่ แต่ใช้คำสั่งเป็น

$ gcc -Wall -o prog2 main2.c func2.c

จะมี warning มาเตือนว่าไม่ได้มีการกำหนด function prototype ของฟังก์ชัน sum

main2.c:7:2: warning: implicit declaration of function ‘sum’ [-Wimplicit-function-declaration]

เมื่อไม่ประกาศ function prototype เอาไว้ คอมไพเลอร์ก็จะไม่ตรวจสอบ type ของ argument ที่ส่งไปที่ฟังก์ชัน และไม่มีการแปลง type ให้ตรงกับที่ฟังก์ชันต้องการ ดังนั้นเมื่อเรียกใช้งานฟังก์ชัน sum โดยกำหนดค่า 5.0 และ 10.0 ซึ่งมี type เป็น double ให้ ก็จะเอา binary representation ของ double ส่งไปให้ฟังก์ชัน แต่ฟังก์ชันบวกเลขแบบ int และส่งค่ากลับเป็น int ผลที่ได้ก็จะประหลาดๆ แบบนี้ที่เห็น

ถ้าต้องการให้ถูกต้อง เราก็จะต้องประกาศ function prototype ของฟังก์ชัน sum เอาไว้ใน main2.c เพื่อให้คอมไพเลอร์รู้ว่าฟังก์ชัน sum รับ argument 2 ตัวเป็น int ทั้งคู่ และจะส่งค่ากลับมาเป็น int คอมไพเลอร์ก็จะแปลงค่า 5.0 และ 10.0 ให้เป็น binary representation แบบ int ก่อนแล้วค่อยส่งไปยังฟังก์ชัน ทำให้ได้ผลลัพธ์ตามต้องการ (จริงๆ ต้องใช้ว่าใกล้เคียงกับที่ต้องการ เพราะการแปลงจาก double ไปเป็น int อาจจะทำให้ค่าของข้อมูลหายไปได้)

Function prototype นี้จะเขียนแยกต่างหาก เป็น header file (.h) ก็ได้ เพื่อความสะดวกในการนำ func2.c ไปใช้กับโปรแกรมอื่นๆ ได้อีก ไม่จำเป็นต้องยึดติดกับ main2.c เลยกลายเป็น 3 ไฟล์ใหม่นี้

/* main3.c */
#include<stdio.h>
#include"func3.h"
main() {
 int i;

 i = sum(5.0, 10.0); 
 printf("sum = %d\n", i);
}

/* func3.c */

int sum(int a, int b) {
 return a+b;
}

/* func3.h */
int sum(int, int);

เติมอีกหน่อยว่าตัวอย่างแรกในตอนที่แล้วทำงานได้ถูกต้อง เพราะไม่มีการส่ง argument ไป และค่าส่งกลับที่เป็น int นั้น เป็น type ปกติอยู่แล้ว

วันนี้เอาแค่นี้ก่อนละกัน พรุ่งนี้ค่อยมาต่อเรื่อง extern