Theppitak's blog

My personal blog.

29 ธันวาคม 2565

From C++ to Rust So Far

บันทึกเมื่อเรียน Rust ได้ครึ่งทาง

ผมเคยเรียน Rust ไปแล้วรอบหนึ่ง ตอนนั้นเรียนจากเว็บไหนก็จำไม่ได้ เขียนบนเว็บ คอมไพล์บนเว็บ ไม่เหลือร่องรอยในเครื่องให้ทบทวน แถมเนื้อหาก็ไม่ได้ลงลึกอะไร เรียนเหมือนไม่ได้เรียน ความมึนไม่ปรากฏ และไม่นานก็ลืม รอบนี้จึงขอเรียนแบบจริงจังเพื่อหวังให้นำไปใช้ได้จริง หลังจากที่ได้เห็นการใช้งานที่หลากหลายของภาษาในที่ต่างๆ จนดูเหมือนพยายามจะแทนที่ C/C++ ให้ได้

ครั้งนี้ผมเลือกที่จะเรียนแบบมี quiz จากแหล่งซึ่งมีเนื้อหาเดียวกับหนังสือ The Rust Programming Language (the book) แต่แทรก quiz เป็นระยะ

ซึ่งผมขอวิจารณ์ว่าเนื้อหายังอธิบายประเด็นสำคัญไม่ละเอียดเท่าที่ควร บางเรื่อง เช่น syntax ของ reference อ่านแล้วยังไม่เกิดความมั่นใจว่าเมื่อไรควรใช้แบบไหน ในขณะที่ quiz ซึ่งควรจะช่วยตรวจสอบความเข้าใจได้กลับมีหลายข้อที่ถามเกินเนื้อหาปัจจุบัน ทำให้วัดอะไรไม่ได้ และยังทำให้เกิดความไม่มั่นใจในสิ่งที่เรียน แต่หลายข้อที่ถามไม่เกินเนื้อหาก็ช่วยทบทวนได้ดีเหมือนกัน และบางข้อยังบ่งชี้ได้ว่าเนื้อหาที่อธิบายไปนั้นยังขาดรายละเอียดบางอย่าง จึงขอแนะนำผู้ที่จะเรียนจากแหล่งนี้ว่าพยายามทำ quiz เท่าที่ทำได้ แต่ถ้าทำไม่ได้เพราะข้อมูลยังไม่เพียงพอก็ไม่ต้องเสียกำลังใจ ข้ามๆ ไปบ้างก็ได้ แล้วค่อยกลับมาดูทีหลังเมื่อได้เรียนเพิ่มเติม

หลังจากเรียนมาได้ประมาณครึ่งหนึ่งของจำนวนบททั้งหมด ก็ขอเขียนบันทึกระหว่างทางสักหน่อยเกี่ยวกับประเด็นของ Rust ที่คิดว่าน่าสนใจ

Ownership

ด้วยความรู้ครึ่งทางนี้ ผมได้เห็นความพยายามของ Rust ที่จะจัดการ memory แบบไม่ใช้ garbage collection โดยขจัดปัญหา memory leak หรือ memory corruption ต่างๆ ที่พบใน C/C++ โดยเฉพาะใน C โดยเครื่องมือหลักที่ใช้คือ ownership ที่ฝังไว้ในตัวภาษาเลย

เวลาเขียน C เราจะสร้าง contract ต่างๆ ของ API ว่า object ต่างๆ ที่สร้างขึ้น เป็นหน้าที่ของใครในการทำลาย โดยเขียนไว้ใน API documentation และเป็นเรื่องของนักพัฒนาที่ ควร พยายามทำตาม บางครั้งมีการถ่ายโอนความรับผิดชอบในการทำลายไปให้ object อื่นก็ควรทำให้ชัดเจน โครงการไหนที่มีการจัดการเรื่องนี้ดีก็จะปลอดปัญหา แต่ถ้ามีจุดผิดพลาด ก็กลายเป็นการเขมือบทรัพยากรระบบ หรือทำให้โปรแกรมตาย หรือกระทั่งโดนจารกรรมข้อมูลได้ โดยมีการพัฒนาเครื่องมือต่างๆ มาช่วยตรวจสอบ เช่น valgrind

ถ้าเป็น C++ ก็มี constructor/destructor รวมถึง smart pointer ต่างๆ มาช่วยจัดการให้ ก็สะดวกกว่า C ขึ้นมาหน่อย แต่ก็ยังอาศัย วินัย ของโปรแกรมเมอร์บ้างอยู่ดี การแยก composition/aggregation ออกจาก association ใน class diagram ก็เพื่อสื่อสารเรื่องนี้

แต่ Rust กำหนดเรื่องนี้ไว้ในตัวภาษาเลย เรียกว่า ownership และใช้ move semantics เป็นหลักใน assignment และการ pass argument ทำให้มีการถ่ายโอน ownership เพื่อลดการ clone โดยไม่จำเป็น โดยที่ยังมี reference คล้ายของ C++ ให้ใช้ในกรณีที่แค่ ยืมใช้ (borrow) โดยไม่ take ownership โดยทั้งหมดนี้มีการตรวจสอบให้ตั้งแต่ตอนคอมไพล์!

ตอนที่เรียนเรื่องนี้ก็รู้สึกว่าเป็นความกล้าหาญมากที่ Rust พยายามจัดการ memory ด้วยคอมไพเลอร์ และถ้าทำได้จริงโดยไม่เพิ่มความยุ่งยากเกินไปก็เป็นเรื่องดี แต่ในใจก็สงสัยว่าจะทำได้แค่ไหน มีอะไรต้องแลกแน่ๆ ซึ่งก็เป็นไปตามนั้น เยอะเสียด้วย มันเหมือนการเลือก program design แบบหนึ่งที่อาจมีในโครงการ C/C++ บางโครงการ แล้วบังคับให้ใช้แบบนั้นไปเลย โดยบัญญัติเป็น syntax และ semantics ของภาษา โปรแกรมเมอร์ภาษา Rust ซึ่งเรียกว่า Rustacean (มันคือ Crustacean หรือสัตว์พวกกุ้งกั้งปูที่ไม่เขียน C? :P) ต้องใช้โหมดความคิดอีกโหมดหนึ่งในการเขียนโปรแกรมไปเลย

และขอบอกว่าสมัยที่เรียน C นั้น ผมไม่เคยมึนกับ pointer ของ C เท่ากับที่มึน ownership ของ Rust เลย! ตอนที่เขียน C นั้น ownership ต่างๆ เกิดจากวินัยที่เราสร้างขึ้นเองจากความเข้าใจ แต่พอมันกลายเป็นข้อบังคับของภาษา มันจะเหมือนการเดินที่ต้องคอยระวังไม่ให้เหยียบมดหรือกระทั่งทำให้มดตายทางอ้อม ขนาดนั้นเลย

Safe Borrows

บ่อเกิดของความมึนคือ Rust มีการสับรางการยืมไม่ให้เกิด race condition โดยอนุญาตให้มีการยืมแบบอ่านอย่างเดียว (immutable borrow) ได้พร้อมกันหลายทาง แต่ทันทีที่มีการยืมแบบเขียนได้ (mutable borrow) เกิดขึ้น การยืมอื่นทุกทางจะหมดอายุทันที ไม่ว่าจะยืมแบบเขียนได้หรือไม่ได้ และถ้ามีการใช้การยืมที่หมดอายุแล้ว ก็จะเกิด error ทันที โดยเป็น error ที่ตรวจพบตั้งแต่ตอนคอมไพล์!

การตรวจสอบนี้ ช่วยป้องกันบั๊กอย่างเช่นมีการลบ element ในลูปที่ iterate ใน vector เพราะการลบ element ต้องยืม vector แบบ mutable ทำให้ iterator ที่กำลังยืม vector อยู่เหมือนกันไม่สามารถ iterate ต่อไปได้ หากต้องการลบ element ในลูปจริงๆ ก็คงต้องเลี่ยงไปใช้ indexing แทน ซึ่งปลอดภัยกว่า เป็นต้น

ฟังดูเหมือนไม่มีอะไร แต่เอาเข้าจริงเวลาอ่านโค้ดมันซับซ้อนว่ามีการยืมซ่อนอยู่ที่ไหน ใครหมดอายุตอนไหน เวลาทำ quiz จะมึนมาก แต่เวลาคอมไพล์จริง error message ช่วยได้เยอะมาก

Lifetime

ใน C/C++ มีบั๊กประเภท dangling pointer หรือ use after free ที่เกิดจากการ dereference pointer ชี้ไปยัง object ที่ถูกทำลายไปแล้ว Rust ป้องกันปัญหานี้ด้วยการกำหนด lifetime ของ object ทำให้การใช้ reference ที่นอกจากไม่อนุญาตให้เป็น null แล้ว ยังไม่อนุญาตให้ reference ไปยัง object เกินอายุขัยของ object ด้วย ถ้าตรวจพบก็จะมี compiler error เช่นกัน!

จากสามเรื่องข้างต้น น่าทึ่งที่ Rust พยายามขนาดนี้เพื่อป้องกันปัญหา memory ตั้งแต่ตอนคอมไพล์ สิ่งที่แลกมาคือคุณต้องใช้ความระมัดระวังอย่างหนักในการเขียนโค้ด ซึ่งบางครั้งกฎเหล่านี้ยังครอบคลุมไปถึงกรณีที่พิสูจน์ได้ว่าปลอดภัยด้วย แต่ถ้ามันแหกกฎของ Rust ก็ถูกตีตกได้

ยังมีเรื่องอื่นที่ขัดกับความรู้สึกของคนที่มาจากภาษา C/C++

The Default Immutability

ในขณะที่ C/C++ และภาษาอื่นจำนวนมากใช้ ตัวแปร เพื่อการคำนวณ โดยปกติตัวแปรจึงสามารถเปลี่ยนค่าได้ ยกเว้นเมื่อต้องการห้ามเปลี่ยนจึงใส่ qualifier const กำกับ แล้วคอมไพเลอร์จะช่วยโวยวายให้ถ้ามีความพยายามจะเปลี่ยนค่าที่กำหนดเป็น const ไว้ แต่ Rust จะให้ตัวแปรเป็น const หรือ immutable โดยปริยาย เมื่อต้องการเปลี่ยนค่าจึงใส่ keyword mut (mutable) กำกับ นัยว่าเป็นการเอื้อต่อ functional programming และ concurrency กระมัง? แต่ในแง่หนึ่งก็เป็นการเน้นให้เห็นชัดเจนว่าค่าไหนมีโอกาสถูกเปลี่ยน เช่นตอนที่ให้ฟังก์ชัน ยืม object ไป อาจมีการเปลี่ยนค่าใน object นั้นกลับมา ซึ่งโค้ดที่เขียนด้วย C/C++ จำนวนมากที่ไม่ค่อยเคร่งครัดการใช้ const ก็จะเห็นเรื่องนี้ได้ไม่ชัด แต่กับ Rust ถ้าไม่เคร่งครัดคุณก็หมดสิทธิ์เปลี่ยนค่า ซึ่งก็อาจจะดี แต่คุณจะเผลอสับสนกับโหมดความคิดอยู่บ่อยๆ

The Default Move Semantics

ใน C++11 มีสิ่งที่เรียกว่า move semantics ซึ่งใช้ย้ายข้อมูลจาก object หนึ่งไปยังอีก object หนึ่งที่เป็น class เดียวกันพร้อมกับล้างค่าใน object ต้นทาง ทำให้เกิดการย้าย ownership โดยไม่มีสำเนาเกิดขึ้น ซึ่งนอกจากจะช่วยจัดการ ownership แล้ว ยังช่วยลดการ clone และ destruct โดยไม่จำเป็นอีกด้วย เพราะ move constructor สามารถย้ายเฉพาะ pointer ที่ชี้ data ได้เลย ไม่ต้องสำเนาตัว data ใน object ใหม่ และทำลาย data ใน object เก่า โปรแกรม C ที่ออกแบบดีๆ ก็สามารถ move data ในลักษณะนี้ได้เช่นกัน แต่เรื่องนี้ก็ยังไม่ใช่ default ของทั้ง C และ C++ ต้องมีการทำอะไรบางอย่างเพิ่มเติมเพื่อจะใช้ เช่น ใน C++ ก็ใช้ std::move()

แต่ Rust ใช้ move semantics โดยปริยาย ทั้งใน assignment และ function call ยกเว้นว่าต้องการทำสำเนาจึง clone เอา หรือแค่ให้ยืมผ่าน reference เอา ซึ่งก็อาจทำให้โค้ดโดยรวมมีประสิทธิภาพขึ้น แต่คุณก็ต้องระวังผลของการเปลี่ยนแปลง ownership ที่เกิดขึ้นด้วย

นอกจากนี้ ก็มีหลายสิ่งที่เป็นประโยชน์ใน Rust

Enum as Tagged Union

เวลาใช้ union ใน C/C++ เรามักใช้ร่วมกับ field ที่ระบุว่าเราใช้ข้อมูลชนิดไหนใน union นั้น ซึ่งเคยเห็นบางตำราเรียกว่า tagged union

Rust เอาสิ่งนี้มารวมเข้ากับ enum โดยกำหนดให้ enum สามารถมีข้อมูลประกอบได้ ซึ่งหาก implement ด้วย C/C++ ก็คือการใส่ union ประกอบกับ enum เป็น tagged union นั่นเอง ทำให้สร้าง tagged union ใน Rust ได้สะดวกสบาย ไม่ต้องเขียนโค้ดในการอ่าน/เขียนเอง

Option, Result

Rust ลงทุนสร้าง enum แบบมีข้อมูลประกอบ ก็นำมาใช้ประโยชน์กับค่า return ของฟังก์ชันที่สามารถ return ทั้งสถานะ success/failure และผลลัพธ์ที่ได้ในคราวเดียว

Option คือ enum ที่มีสองค่า คือ None กับ Some โดยค่า Some สามารถมีข้อมูลประกอบได้ ใช้กับฟังก์ชันที่ทำอะไรสักอย่างให้ได้ผลลัพธ์โดยอาจล้มเหลวได้ เช่น การค้นหาข้อมูล ในภาษา C/C++ เราอาจให้ฟังก์ชัน return สถานะ success/failure และถ้า success ก็เขียนข้อมูลลงใน parameter ที่ call by reference มา เช่น

bool Table::FindData(const char* key, Record& result) const;

หรืออีกแบบคือ return pointer ไปยัง object ที่สร้างขึ้นใหม่ โดยถ้าล้มเหลวก็ return NULL

Record* Table::FindData(const char* key) const;

แต่ Rust ไม่มี null pointer/reference แต่จะ return เป็น Option มาเลย

impl Table {
    pub fn find_data(&self, key: &str) -> Option<Record> {
        ...
    }
}

โดยผู้เรียกจะตรวจสอบค่า enum ที่ return มาก่อนดึงค่าออกมาใช้ก็ได้ หรือจะใช้ method ของ Option ในการแกะห่อเอาค่ามาใช้ก็ได้ ซึ่งเป็นวิธีที่ถือว่าดูดี

Result ก็คล้ายกัน คือเป็น enum ที่มีสองค่า คือ Ok กับ Err โดยค่า Ok สามารถมีข้อมูลผลลัพธ์ประกอบได้ และค่า Err ก็มีข้อมูล error ประกอบได้ (ต่างกับ None ของ Option ที่ไม่มีข้อมูลประกอบใดๆ)

Trait-Bound Generic

trait คือสิ่งที่คล้ายกับ interface ในภาษา OOP ต่างๆ แต่ไม่เหมือนกันเสียทีเดียว

generic ก็เหมือนกับ template ของ C++ ซึ่งหากใครเคยใช้ STL ของ C++ จะรู้ว่า type ที่จะมาเป็น parameter ของ template หนึ่งๆ มักมีข้อแม้บางอย่าง แล้วแต่ template ที่ใช้ เช่น ต้องเปรียบเทียบค่ากันได้ หรือต้องรองรับการ move ฯลฯ แต่ไม่เคยมีการประกาศชัดเจน จะรู้ได้ก็ตอนที่คอมไพเลอร์ฟ้องว่าขาดคุณสมบัติ แล้วค่อยไปหาทางอุดทีละเรื่องเอา (ผมว่านี่แหละคือสิ่งที่คล้ายกับ duck typing ใน C++)

แต่ generic ของ Rust สามารถประกาศคุณสมบัติของ type ที่เป็น parameter ได้ว่าต้องรองรับ trait ใดบ้าง ทำให้รู้แต่ต้นว่าต้องเตรียมคุณสมบัติอะไรไว้

Rust ยังมีรายละเอียดให้เรียนรู้อีกเยอะ นี่ผมเพิ่งมาได้ครึ่งทาง ก็ยังต้องเรียนรู้กันต่อไป

ป้ายกำกับ: , ,

23 ตุลาคม 2564

IBus-LibThai 0.1.5

IBus-LibThai 0.1.5 ออกไปแล้วเมื่อวันพุธที่ผ่านมา หลังจากไม่มี release มาเกือบ 5 ปี โดยมีเงื่อนไขหลักที่ทำให้จำเป็นต้องออกรุ่นใหม่คือปัญหาในระบบตั้งค่า อาการคือตั้งค่าเสร็จแล้วไม่มีผลต่อตัว engine ตั้งยังไงก็ได้ค่า default

ผมไม่ได้ติดตามการพัฒนาของ IBus มาระยะหนึ่ง จึงไม่ทราบว่ามีความเปลี่ยนแปลงอะไรบ้างจนทำให้วิธีตั้งค่าแบบเดิมใช้ไม่ได้ จึงเริ่มจากตรวจสอบ engine อื่นว่าปัจจุบันเขาทำยังไงกัน ก็ได้พบว่าหลาย engine ได้ย้ายจากการใช้ IBusConfig ซึ่งเป็น API ของ IBus เองสำหรับการจัดการค่าตั้งไปใช้ระบบอื่น บาง engine ถึงกับสร้างระบบ config ของตัวเองขึ้นมาเลย

แต่ผมก็ยังคงพยายามปรับแก้ภายใต้ API ของ IBus ต่อไป โดยเปลี่ยนจากการ restart IBus เพื่อ reload config มาเป็นการ watch ค่า config แล้วปรับใช้ค่าที่เปลี่ยนทันทีแทน ซึ่งก็ทำให้ engine เปลี่ยนพฤติกรรมตามค่าที่ผู้ใช้ตั้งได้ ภายใน session เดิม แต่ไม่สามารถ save ค่าไว้ให้มีผลใน session ถัดไปได้

ผมแน่ใจว่าทำทุกอย่างเท่าที่ document บอกแล้ว ถ้าจะมีอะไรที่ undocumented ก็ต้องแกะซอร์สของ IBus ซึ่งพอลงมือแกะก็พบว่า แม้แต่ IBus แกนหลักเองก็ไม่ใช้ IBusConfig แต่ไปใช้ GSettings ของ GLib!

จะรออะไรล่ะครับ ถึงแกะจนเจอที่ผิด แต่เขาจะสนใจแก้โค้ดที่เขาเองก็ไม่ใช้ไหมล่ะ? ผมจึงตัดสินใจเปลี่ยนไปใช้ GSettings เหมือนกัน

ด้วยระบบ GSettings ซึ่งใช้ dconf เป็น backend ค่าตั้งต่างๆ จะสามารถเข้าถึงได้ด้วยโปรแกรม dconf-editor

ค่า config ของ IBus-LibThai ใน dconf editor

โดยค่า config แต่ละค่าจะมีคำอธิบายจาก GSchema ที่เตรียมไว้

คำบรรยายคีย์ kb-layout ของ IBus-LibThai ใน dconf editor

และผู้ใช้ IBus ก็ยังคงสามารถปรับแต่ง IBus-LibThai ได้จาก preferences ของ engine ใน IBus Preferences ตามปกติ

Preferences ของ IBus-LibThai

พร้อมกันนี้ ยังมีความเปลี่ยนแปลงอื่นในส่วนของผังแป้นพิมพ์:

  • มีการปรับโครงสร้างของข้อมูลผังแป้นพิมพ์เพื่อให้เข้าใจง่าย และสะดวกต่อการปรับแก้
  • ปรับแก้ผังปัตตะโชติที่ยังคลาดเคลื่อนจากแพลตฟอร์มอื่น โดย ขอหารือ กับคุณ @sirn ซึ่งเป็นผู้ใช้ผังปัตตะโชติ ซึ่งคุณ @sirn ก็ได้เสนอแนะเพิ่มเติม จนกระทั่งได้ตำแหน่งปุ่มสำหรับอักษรไทยเพิ่ม คือ ฃ ขวด, ฅ คน, ลากข้างยาว, ยามักการ
  • เพิ่มผัง มนูญชัย ซึ่งเป็นผังแป้นพิมพ์ใหม่ล่าสุดที่เกิดจากการออปติไมซ์ด้วย AI จากตัวอย่างเอกสารร่วมสมัย ผู้ใช้ลินุกซ์ที่สนใจทดสอบหรือใช้งานผังใหม่นี้จึงสามารถใช้งานได้ผ่าน IBus-LibThai

ป้ายกำกับ: ,

16 กันยายน 2564

Red-Black Trees

Red-black tree เป็น self-balancing binary search tree ที่ใช้ในโครงการต่างๆ มากมาย เช่น ใน C++ STL, ใน symbol table ของ compiler/interpreter ต่างๆ และใน Linux kernel ด้วยข้อได้เปรียบ AVL tree เรื่องการเพิ่มข้อมูลเพื่อการ balance ในแต่ละโหนดเพียงบิตเดียว ในขณะที่ AVL tree ต้องการอย่างน้อย 2 บิต รวมถึงการ insert และ delete ที่เร็วกว่า แม้จะใช้เวลา search มากกว่าสักหน่อย แต่ก็ยังเป็น O(log n) เหมือนกัน

ฟังดูน่าศึกษาใช่ไหมล่ะ? แต่พอลองค้นดูจริงๆ มันยุ่งกว่าที่คิดมาก

red-black tree เสนอโดย Leonidas J. Guibas และ Robert Sedgewick (PDF) โดยต่อยอดมาจาก symmetric binary B-tree ของ Rudolf Bayer

symmetric binary B-Tree เป็นการสร้าง perfectly-balanced 2-3-4 tree (B-tree ที่มีทางแยกไม่เกิน 4 และทุก leaf มีความลึกเท่ากันหมด) ด้วย binary tree แบบพิเศษ โดยแทนโหนด B-tree ที่มีทางแยก 3 และ 4 ทางด้วย binary node 2 และ 3 โหนดที่เชื่อมกันด้วยลิงก์แนวนอน (เรียกว่า ρ-arc) ส่วนลิงก์ที่เชื่อมระหว่างโหนดของ B-tree ก็เป็นลิงก์แนวตั้ง (เรียกว่า δ-arc)

Guibas และ Sedgewick ได้นำ symmetric binary B-tree มาสร้างคำอธิบายแบบใหม่ โดยให้ทุกลิงก์เป็นลิงก์แนวตั้งทั้งหมด และเรียก ρ-arc ของ Bayer ว่า red link และเรียก δ-arc ว่า black link แล้วเรียบเรียงนิยามและอัลกอริทึมต่างๆ เสียใหม่ กลายเป็น red-black tree

Red-black representation of a 2-3-4 tree
(ภาพจาก Left-leaning Red-Black Trees โดย Robert Sedgewick)

ส่วนเหตุผลว่าทำไมต้องเป็นสองสีนี้ Sedgewick ตอบไว้ในตอนท้ายของการบรรยายครั้งหนึ่งว่า เป็นเพราะขณะที่พัฒนาเรื่องนี้กันที่ Xerox PARC นั้น เริ่มมีการสร้าง laser printer ที่สามารถพิมพ์สีได้ และสีที่พิมพ์ออกมาดูดีที่สุดในขณะนั้นคือสีแดง

อัลกอริทึมสำหรับ insert ของ red-black tree ค่อนข้างจะเทียบเคียงกับของ 2-3-4 tree ได้อย่างตรงไปตรงมา และใช้ operation พื้นฐานในการ rebalance คล้ายกับของ AVL tree แต่อัลกอริทึมสำหรับ delete นั้น Guibas และ Sedgewick บรรยายไว้ไม่ยาวมาก และยังดูมีขั้นตอนเกินจำเป็น โดยมีการ rebalance ทั้งขาลงและขาขึ้น

หลายตำราจึงคิดโครงสร้างของตัวเองขึ้นมาเพื่อปรับปรุงการ delete ซึ่งหลายกรณีส่งผลถึงวิธีอธิบายโครงสร้างทั้งหมดที่ไม่เชื่อมโยงกับ 2-3-4 tree อีกต่อไป เช่น เรียก red/black node แทน red/black link และอธิบายโครงสร้างในเทอมของ parent/sibling/uncle node ไปเลย ซึ่งทำให้จำเป็นต้องมี parent pointer และไม่อาศัย recursion และพอมาถึงเรื่องการ delete หลายตำราก็อธิบายได้น่าปวดหัวมาก บางฉบับถึงกับจั่วหัวไว้ก่อนเลยว่า You will hate it! บางฉบับข้ามเรื่อง delete ไปเสียดื้อๆ เลยด้วยซ้ำ

Red-black tree with red/black nodes
Red-black tree ที่ใช้ red/black node
(ภาพจาก Wikipedia)

หลังจากอ่านมาหลายแหล่ง รวมถึงฉบับที่ Sedgewick กลับมาเองด้วยโครงสร้าง Left-leaning red-black tree (slide, Coursera) พร้อมกับโค้ดสุด simple แต่ก็มีปัญหาเรื่องการ delete ที่ช้ากว่าของตำราอื่น ดังบทวิจารณ์ Left-Leaning Red-Black Trees Considered Harmful

แต่สุดท้ายก็เจอคำอธิบายที่ผมคิดว่าลงตัวที่สุดจากคอร์สหนึ่งของมหาวิทยาลัย Purdue ซึ่งอธิบาย Red-black tree แบบไม่มี leaning โดยอิง 2-3-4 tree ตั้งแต่ต้นจนจบ อ่านได้ตามลำดับเลยครับ:

  1. (2,4) Trees
  2. 2-3-4 Trees and Red-Black Trees
  3. Deletion from Red-Black Trees

ป้ายกำกับ: ,

23 มิถุนายน 2564

Norasi Small Caps and Old Style Figures

ฟอนต์ Norasi เพิ่มการรองรับการใช้ small caps และ old style figures (ตัวเลขอารบิกแบบหนังสือยุคเก่า) แล้ว ทั้งใน OpenType และ LaTeX

PUA Glyphs

ฟอนต์ Norasi (ฟช ๓ จากโครงการฟอนต์แห่งชาติของเนคเทค) มี PUA glyph สำหรับตัว small caps และตัวเลขอารบิกในหนังสือยุคเก่า (old style figures) มานานแล้ว ผมไม่แน่ใจว่ามีมาตังแต่แรกเริ่มที่นำฟอนต์มาจากโครงการ Omega เลย หรือว่ามาเพิ่มเอาทีหลังใน TLWG เนื่องจากผู้ที่ทำงานกับ Norasi ในช่วงต้นจะเป็นคุณทิม (ชนพ ศิลปอนันต์) เป็นหลัก แต่มันก็อยู่ในรูป glyph ที่มีรหัสยูนิโค้ดในช่วง Private Use Area (PUA) พร้อมกับชื่อ glyph แบบ Postscript ตามอย่าง Adobe Glyph List เช่น เลขศูนย์แบบเก่ามีรหัสยูนิโค้ด U+F730 และมีชื่อ glyph เป็น zerooldstyle และตัว A small caps มีรหัสยูนิโค้ด U+F761 และมีชื่อ glyph เป็น Asmall เป็นต้น

PUA glyph เหล่านี้ โดยปกติจะไม่ใช้ในข้อความ แต่จะใช้เป็นการภายในของตัววาดข้อความ ในทำนองเดียวกับวรรณยุกต์ตัวต่ำ สระบนหลบหาง ป ฝ ฟ และสระอุ อู หลบหาง ฎ ฏ ในอักษรไทยนั่นเอง เท่ากับว่า PUA glyph เหล่านี้มีอยู่ แต่ยังไม่พร้อมใช้ ยกเว้นในระบบที่พยายามจะใช้ PUA เหล่านี้จริงๆ

OpenType

ขณะเดียวกัน เราจะเห็นแอปพลิเคชันสมัยใหม่พยายามรองรับ OpenType feature ต่างๆ ใน UI มากขึ้น จากเดิมที่มีแต่ใน desktop publishing หรูๆ ตอนนี้แม้แต่ word processor อย่าง LibreOffice Writer และ MS Word ก็เริ่มมี UI สำหรับเลือกเปิด/ปิด discretionary feature (ฟีเจอร์ที่กำหนดใน mark up ของเอกสาร และอาจจะผ่าน UI ให้ผู้ใช้เลือก) ของ OpenType แล้ว ซึ่ง small caps (smcp) และ old style figures (onum) ก็เป็นฟีเจอร์ชนิดนี้

หลังจากเพิ่มฟีเจอร์ดังกล่าวในฟอนต์ Norasi แล้วทดลองใช้กับ LibreOffice Writer ก็ได้ผลดังนี้:

  • บรรทัดแรก เป็นตัวเลขแบบเรียงบนบรรทัด (lining figures)
  • บรรทัดที่ 2 เป็นตัวเลขแบบหนังสือยุคเก่า (old style figures)
  • บรรทัดที่ 3 เพิ่มการใช้ small caps จาก glyph ในฟอนต์เอง ผ่าน scmp โดยเลือกฟีเจอร์ Lower case to small capitals ใน character format
  • บรรทัดที่ 4 ใช้ Small capitals จาก text format ของ LibreOffice เอง ซึ่งน่าจะเป็นการสังเคราะห์ small caps ด้วยการย่อส่วนจากตัว capital ปกติ ซึ่งทำให้ได้เส้นที่บางลง และ LibreOffice ก็ได้พยายามลดผลกระทบนี้ด้วยการย่อส่วนแต่เพียงเล็กน้อย ทำให้ได้ตัว small caps ที่ยังสูงกว่าตัว lower case อยู่

สำหรับการใช้ในเว็บ ผมได้ลองทำ หน้าทดสอบ โดยใช้ font-variant: small-caps และ font-variant-numeric: oldstyle-nums ใน CSS

LaTeX

สำหรับผู้ใช้ XeLaTeX และ LuaLaTeX ก็สามารถใช้ OpenType feature ได้โดยตรง แต่สำหรับ pdfLaTeX ซึ่งยังใช้เทคโนโลยี PostScript ธรรมดา ก็จำเป็นต้องมีการรองรับเพิ่มเติมในแพกเกจฟอนต์

Small Caps

LaTeX2e รองรับ small caps ผ่านคำสั่ง \scshape และ \textsc{...} โดยตัว TeX engine จะไปหาการประกาศ sc shape ใน font description (lthnorasi.fd สำหรับฟอนต์ Norasi) เพื่อเชื่อมโยงไปหาไฟล์ TFM (TeX Font Metrics) ของ shape ดังกล่าว

และตรง TFM นี่แหละ ที่เราสามารถ remap อักขระ lower case ไปหา glyph ที่เป็น small caps ได้ ทำให้ TeX เรียงพิมพ์ตัว lower case ด้วยตัว small caps แทน

เท่ากับว่า จากฟอนต์ Norasi ที่เรามีอยู่แล้ว 6 type face (regular, slanted, italic, bold, bold slated, bold italic) เราจะต้องสร้าง face ใหม่อีกหนึ่งชุดที่ remap สำหรับ small caps กลายเป็น 12 type face

แต่เรายังมีรายละเอียดที่ต้องพิจารณาเพิ่มจากการ remap คือ:

  • ต้องตัดกฎ ligature สำหรับ ff, fi, fl, ffi, ffl ออกด้วย เนื่องจากรูป small caps ไม่มี ligature ดังกล่าว
  • ฟอนต์ไทยใช้กฎ ligature ในการจัดเรียงสระ-วรรณยุกต์ที่ไม่ลอยและหลบหางพยัญชนะ (shaping) ซึ่งยังจำเป็นต้องสร้างกฎเหล่านี้สำหรับ small caps อยู่

นั่นจึงนำไปสู่การสร้างไฟล์ .enc ต่างหากที่ remap small caps, ตัดกฎ Latin ligature, คงกฎ ligature สำหรับอักษรไทย พร้อมทั้งเขียน make rules สำหรับสร้าง TFM (สำหรับ TeX) และ VF (virtual font ซึ่งใช้ในขั้น dvi) สำหรับ small caps เพิ่มอีกชุดหนึ่งด้วย

สรุปรวมอยู่ใน GitHub commit นั่นแล

และเมื่อใช้งานผ่านคำสั่ง \textsc{...} ก็ได้ผลดังภาพ:

Small caps in pdfLaTeX

Old Style Figures

ด้วยเทคโนโลยี PostScript ธรรมดา การรองรับตัวเลขแบบหนังสือยุคเก่า (old style figures) ก็ยังคงต้องใช้วิธี remap อักขระตัวเลขไปเป็น PUA glyph ที่เป็น old style ไม่ต่างกับ small caps เพียงแต่ old style figures จะมีประเด็นการใช้งานในทางปฏิบัติที่ต้องพิจารณาเพิ่มเติมด้วย

LaTeX2e มีคำสั่ง \oldstylenums{ตัวเลข) เพื่อแสดง ตัวเลข เป็นแบบ old style ได้ โดยจะใช้ glyph จากฟอนต์ของ Knuth เสมอ แต่ในกรณีที่ต้องการให้ผู้ใช้สามารถใช้ตัวเลข old style จากฟอนต์ของเราได้ ก็จะต้องใช้ช่องทางอื่น

use case ที่น่าจะพบบ่อยในชีวิตจริง คือการใช้ตัวเลข old style ทั้งเอกสาร ทั้งเลขบท เลขหัวข้อ เลขหน้า เลขในข้อความ ฯลฯ ซึ่งตรงนี้จะต่างจาก small caps และแพกเกจฟอนต์มักจะรองรับในรูปของ option ของแพกเกจ

อีก use case หนึ่งคือการใช้ตัวเลข old style เฉพาะที่ ซึ่งมีแพกเกจอย่างน้อยสองตัวที่เตรียมคำสั่งไว้ให้ คือ nfssext-cfr และ fontaxes ซึ่งทั้งสองแพกเกจจัดเตรียมคำสั่งไว้คนละชุด ซึ่งก็ถือเป็นเรื่องปกติ แต่ที่ไม่ปกติคือทั้งสองแพกเกจเรียกใช้ฟอนต์ต่างกันด้วย!

old style figures ไม่ได้ถูกจัดให้เป็น shape หนึ่งของฟอนต์เหมือน small caps เพราะมันมีผลแค่กับตัวเลข ไม่ใช่ทั้งฟอนต์ วิธี implement จึงไม่ใช่การประกาศ shape ใน font description แต่เป็นการสร้าง font family ใหม่ไปเลย! โดยจะมีข้อตกลงบางอย่างในการตั้งชื่อ family ใหม่ที่ว่านั้น และเมื่อผนวกกับคุณสมบัติ proportional/tabular ของตัวเลขเข้าไปด้วยก็กลายเป็นข้อตกลงที่มีรายละเอียดอีกหน่อย

ปัญหาคือ แพกเกจ nfssext-cfr และ fontaxes ใช้ข้อตกลงคนละชุดกัน!

  • nfssext-cfr ใช้ font naming ของ Karl Berry ซึ่งออกแบบมาเพื่อแทนชื่อฟอนต์ให้ได้ใน 8 ตัวอักษร case-insensitive ซึ่งหมายถึงระบบแฟ้มของ DOS นั่นเอง โดยใน 8 ตัวอักษรจะแทนทั้งผู้ผลิต (foundry), ชื่อฟอนต์, ความหนา, variant (เช่น italic, oblique, sans serif, monospace, small caps, old style figures ฯลฯ), encoding, ความกว้าง, ขนาด ซึ่งน่าอัศจรรย์มากกับความพยายามบีบอัดขนาดนั้น แต่ดูไม่ practical เท่าไรกับโลกที่มีฟอนต์มากมายมหาศาล อีกทั้งระบบแฟ้มส่วนใหญ่ในปัจจุบันก็รองรับความยาวเกิน 8 ตัวอักษรกันแทบทั้งสิ้นแล้ว และจะว่าไป ชื่อฟอนต์บางชื่อที่ลงรหัสแบบนี้ก็ยาวเกิน 8 ตัวอักษรไปแล้วด้วย แต่อย่างไรก็ดี มันก็ยังถือเป็นข้อตกลงที่ใช้กันเป็นมาตรฐานของ LaTeX อยู่ และฟอนต์ Norasi ที่ใช้ old style figures ก็จะลงรหัสชื่อ font family (แบบไม่ได้ตรงหลักการเป๊ะ) ได้เป็น norj และ font family แบบปกติก็จะถูกย่อลงเป็น norx (ว่าตามนัยประวัติ ฟอนต์ Norasi ใน ThaiLaTeX ยุคเริ่มแรกก็เคยใช้ชื่อว่า nf3x ก่อนที่จะเปลี่ยนเป็น norasi ในภายหลัง)
  • fontaxes ใช้ข้อตกลงชื่อฟอนต์ของตัวเอง โดยปล่อยชื่อฟอนต์ให้ยาวตามปกติ แล้วเติมท้ายด้วยรหัส variant เช่น Norasi-OsF โดย variant ที่เกี่ยวกับตัวเลขได้แก่
    • OsF = old style figures
    • LF = lining figures
    • TOsF = tabular old style figures
    • TLF = tabular lining figures
    โดยที่ก็ยังรองรับ font naming ของ Karl Berry ด้วย เพียงแต่ไม่ได้บีบความยาวลงเท่านั้น ดังนั้น ตามข้อตกลงนี้ ฟอนต์ Norasi ที่ใช้ old style figures ก็จะใช้ชื่อ font family เป็น norasi-TOsF, norasi-OsF หรือ norasij ก็ได้ เพราะอันที่จริง ตัวเลขในฟอนต์ Norasi เป็น tabular อยู่แล้ว คือกว้างเท่ากันหมด เรียงตรงกันในตารางได้ แต่การใช้ norasi-TOsF จะใช้ได้กับการ mark up ตัวเลขเป็น tabular figures เท่านั้น ใช้ในข้อความธรรมดาไม่ได้ ส่วน norasi-OsF จะใช้ได้ในข้อความธรรมดาและการ mark up เป็น proportional figures เท่านั้น ใช้แบบ tabular ไม่ได้ แต่ norasij จะใช้ได้หมดทุกกรณี ดังนั้น ในกรณีของ Norasi จึงเลือกใช้ชื่อ norasij

จากหลักการทำงานและจากการทดลอง fontaxes ดูจะใช้ได้ในทางปฏิบัติมากกว่า จึงเลือกรองรับ fontaxes เป็นหลัก แต่ก็พยายามรองรับ nfssext-cfr ด้วยตามสมควร

จาก 12 type face ที่ได้จากการทำ small caps มาแล้ว เราก็จะสร้าง font family ใหม่ที่ประกอบด้วย 12 type face นี้ แต่ remap glyph ของตัวเลขไปเป็นแบบ old style เท่ากับว่าเราจะมีทั้งหมด 24 type face แบ่งเป็น 2 family, family ละ 12 type face

เมื่อเขียน make rules เพื่อสร้าง TFM/VF ของ 12 type face ฉบับ old style figures แล้ว เราก็สร้าง LTHnorasij.fd เพื่อประกาศ font family norasij

เพื่อการรองรับ nfssext-cfr เราก็สร้าง LTHnorj.fd ในทำนองเดียวกัน และสร้าง LTHnorx.fd ที่มีเนื้อหาหลักเหมือน LTHnorasi.fd ทุกประการด้วย

ทั้งหมดนี้ก็จะสามารถรองรับใช้ตัวเลขแบบ old style ผ่าน fontaxes และ nfssext-cfr (บางส่วน) ได้แล้ว

Old style figures via fontaxes

Old style figures via nfssext-cfr

สำหรับ use case การใช้ตัวเลข old style ทั้งเอกสาร นั้น เราก็เพิ่ม option norasi-osf และ rmnorasi-osf ใน fonts-tlwg.sty โดยหากเลือกตัวเลือกนี้ก็จะกำหนดฟอนต์ปริยายเป็น norasij แทน norasi เท่านั้นเอง

Old style figures with 'norasi-osf' option

ทั้งหมดนี้อยู่ใน Git แล้ว มีตัวอย่างเอกสารในไดเรกทอรี latex/examples/ คือ:

  • oldnum.tex ใช้ตัวเลขแบบ old style ทั้งเอกสาร และใช้ small caps ในชื่อ section
  • digits-axes.tex ใช้ตัวเลขแบบ old style ผสมกับแบบ lining ผ่าน fontaxes พร้อมทั้งสาธิตการใช้ตัวเลขแบบ tabular/proportional ในตาราง
  • digits-cfr.tex ใช้ตัวเลขแบบ old style ผสมกับแบบ lining ผ่าน nfssext-cfr ซึ่งการใช้ตัวเลขแบบ tabular old style จะยังไม่ทำงาน

หลังจาก make install แล้ว สามารถใช้คำสั่ง make กับไฟล์ PDF ปลายทางได้เลย เช่น make oldnum.pdf

งานนี้สำเร็จลุล่วงได้ ขอให้เครดิตแก่พี่เลี้ยงที่มาช่วยดูแลพ่อ ทำให้ผมสามารถปลีกเวลามานั่งทำงานได้บ้าง

ป้ายกำกับ: , ,

07 มกราคม 2563

Fine-tuning Quadratic Splines in Fontforge

นับจากที่ได้เพิ่ม layer ผสมใน Fonts-TLWG เพื่อแก้ปัญหาเรื่อง build reproducibility ในรุ่น 0.7.0 ก็ได้เปิดช่องทางสำหรับการ fine-tune quadratric spline ของฟอนต์ TrueType เพียงแต่ผมยังไม่ได้ทำกับ Fonts-TLWG ในทันที เพราะได้กลับไปทำ layer ผสมกับ Fonts-Arundina เสียก่อน และได้ถือโอกาสทดลอง fine-tune quadratic spline ต่อด้วย

หลังจากที่เพิ่ม layer ผสมกับทุกฟอนต์ในชุด Arundina แล้ว ก็ได้ทดลอง fine-tune quadratic spline ต่อ ซึ่งก็ทำเสร็จแค่ Arundina Sans เท่านั้น พอมาทำ Arundina Sans Mono ต่อ ปรากฏว่าเกิดเหตุ Fontforge ตายกลางคันขณะ save ทำให้ข้อมูลที่แก้ไขมาได้ครึ่งทางแล้วสูญหายทั้งหมด แม้แต่กระบวนการ recovery ของ Fontforge เองก็กู้ข้อมูลขึ้นมาไม่ได้! ถ้าจะเริ่มใหม่ก็ต้อง check out ฉบับที่ยังไม่ปรับเส้นจาก git ออกมาทำใหม่นั่นแหละ

เป็นอุทาหรณ์ว่าควร commit git ให้บ่อยกว่านี้ ถึงยังไม่เสร็จก็ควร commit ไว้ก่อน แล้วค่อยใช้ option --amend ในครั้งต่อ ๆ ไปก็ยังได้!

ก็เลยตัดสินใจหยุดทำ Arundina ไว้แค่นั้น แล้วเตรียมตัดออกรุ่นใหม่เสียก่อน โดยขอบันทึกสิ่งที่ได้เรียนรู้จากการปรับเส้นฟอนต์ Arundina ไว้ ณ ที่นี้ก่อน ก่อนที่จะนำไปใช้กับ Fonts-TLWG ต่อไป

ปรับ Quadratic และ Cubic Spline ไปด้วยกัน

ในระยะแรกนั้น ผมปรับเฉพาะ quadratic layer เข้าหา cubic layer โดยพยายามให้ curve ทาบกับ cubic layer ได้สนิทด้วยจำนวนจุดที่พอเหมาะ โดยตัดจุดที่ไม่จำเป็นออก และเติมจุดบางจุดที่เห็นว่าน่าจะเป็นประโยชน์ต่อการ hint แต่เมื่อได้ปรับไปเรื่อย ๆ ก็ได้พบกรณีที่ต้องปรับ cubic layer ควบคู่กันมากขึ้นเรื่อย ๆ จนในที่สุดผมก็ปรับทั้งสอง layer ควบคู่กัน ซึ่งปรากฏว่าคุณสมบัติของโค้งทั้งสองแบบได้เสริมกันและกันในการจัด control point ต่าง ๆ ได้เป็นอย่างดี

การปรับทั้งสอง layer ควบคู่กันยังมีข้อดีอีกอย่าง คือเราสามารถลดปริมาณงานในอนาคตหากมีการ copy ข้ามจาก cubic layer มายัง quadratic layer อีกด้วย เพราะจะได้จำนวนจุด quadratic ที่เหมาะสมทันที ไม่ต้องมานั่งปรับใหม่ รวมถึงกรณีที่ต้องการ generate ฟอนต์ TrueType ด้วยการแปลงจาก cubic layer กลางอากาศ (อย่างที่เราเคยทำในสมัยก่อน)

หรือแม้กระทั่งสำหรับการ generate ฟอนต์ PostScript หรือฟอนต์ OpenType ที่ใช้ cubic spline เอง ก็จะได้โค้งที่ได้สมมาตรสวยงาม และยังอาจช่วยให้ rasterize ได้เร็วขึ้นสำหรับบาง engine ได้อีกด้วย (เช่น สำหรับ rasterizer ที่ render Bézier curve ด้วยการแบ่งครึ่ง curve แบบ recursive บนพื้นฐานของ De Casteljau’s algorithm)

ส่วนวิธีการปรับนั้นจะกล่าวถึงต่อไปเป็นลำดับ

Quadratic Spline ใน Fontforge

จากที่ผมเคยเขียนเปรียบเทียบ quadratic และ cubic spline ไว้เมื่อนานมาแล้ว ทั้งในแง่คณิตศาสตร์ การแปลงระหว่างกัน จำนวนจุดที่ใช้แทนโค้ง และการแก้ไข โดยในส่วนของการแก้ไขนั้น ผมได้กล่าวไว้ว่าโค้ง quadratic แก้ไขยากกว่า เพราะการแก้ไขแต่ละจุดจะกระทบถึงจุดข้างเคียงเสมอ แต่ Fontforge มีสิ่งที่ช่วยคลายความอึดอัดตรงนี้ ด้วยจุดต่อโค้งชนิด interpolated ที่ตำแหน่งของจุดต่อโค้งจะคำนวณจากจุดควบคุมข้างเคียง ทำให้ลดการกระทบกระทั่งลงได้

จุด interpolated ในที่นี้ขอเรียกว่า จุดกะ ในโค้ง quadratic เป็นจุดต่อโค้ง (curve point) ที่อยู่กึ่งกลางระหว่างจุดควบคุมสองจุด และในทางกลับกัน จุดต่อโค้งที่มีแขนสองข้างยาวเท่ากันก็จะถือเป็นจุดชนิด interpolated โดยอัตโนมัติใน Fontforge เช่นกัน (ยกเว้นจุดที่ผู้ใช้กำหนดให้ห้าม interpolate)

Quadratic interpolated point

ความพิเศษของจุดกะนี้ก็คือ การแก้ไขจุดควบคุมข้างหนึ่งจะไม่ส่งผลกระทบถึงจุดควบคุมอีกข้างหนึ่ง เพียงแต่จะทำให้ตำแหน่งของจุดกะเองเปลี่ยนไปเป็นจุดกึ่งกลางใหม่ ซึ่งทำให้เกิดผลคล้ายกับการแก้ไข cubic spline โดยไม่ต้องสนใจการมีอยู่ของจุดกะ

Editing with quadratic interpolated point

การประมาณ Cubic Curve ด้วย Quadratic Curve

ดังที่ได้กล่าวไว้ใน blog เดิม ว่าการแปลง quadratic curve เป็น cubic จะเป็นการแปลงแบบแม่นตรง แต่ในทางกลับกัน คือจาก cubic curve เป็น quadratic จะเป็นการประมาณเท่านั้น เนื่องจาก quadratic curve มีความเป็นอิสระ (degree of freedom) น้อยกว่า ดังนั้น เมื่อคุณคัดลอก spline จาก cubic layer มา quadratic layer จึงมีการประมาณค่าเกิดขึ้น

มีอัลกอริทึมจำนวนหนึ่งสำหรับประมาณ cubic curve ด้วย quadratic เช่น แบ่ง curve เป็นส่วนย่อย ๆ ที่เมื่อตัดสัมประสิทธิ์ดีกรีสามออกแล้วได้ quadratic curve ที่ใกล้เคียงพอ (มี paper ที่คล้ายกัน), แบ่งครึ่ง curve ที่ t=0.5 แล้ว solve หาจุดควบคุม quadratic curve ที่ใกล้เคียงของทั้งสองส่วน ฯลฯ

สำหรับ Fontforge แล้ว ใช้การประมาณด้วยจุดกะ โดยอยู่บนพื้นฐานของทฤษฎีซึ่งพบจากการทดลองแต่ยังไม่มีข้อพิสูจน์ทางคณิตศาสตร์ว่า ถ้าแบ่ง cubic curve เป็นช่วง ๆ ด้วย parameter ที่ห่างเท่า ๆ กันแล้ว ปรากฏว่าจุดแบ่งเหล่านั้นจะอยู่กึ่งกลางระหว่างจุดควบคุมข้างเคียงพอดี ซึ่งหมายความว่าสามารถแทนจุดแบ่งทุกจุดด้วยจุดกะได้ ด้วยทฤษฎีนี้ Fontforge จึงประมาณ cubic spline ด้วย quadratic spline ที่เติมจุดกะตามแนวเส้นโค้งเสมอ

Cubic spline approximation with quadratic spline

Fontforge จะพยายามประมาณโค้งโดยเติมจุดกะให้น้อยที่สุด ยิ่งไม่ต้องเติมจุดกะเลยยิ่งดี แต่หากยังคลาดเคลื่อนมากก็ลองเติมหนึ่งจุด สองจุด สามจุด ไปเรื่อย ๆ จนกว่าความคลาดเคลื่อนจะอยู่ในขอบเขตที่กำหนด

การลดจำนวนจุดกะใน Quadratic Curve

การประมาณของ Fontforge คือการประมาณในทางคณิตศาสตร์ที่มีความแม่นยำสูง แต่ในทาง design แล้ว เราอาจยอมรับความคลาดเคลื่อนได้บ้างโดยไม่ทำให้รูปตัวอักษรเพี้ยนไปจากเดิม ซึ่งแน่นอนว่าเรื่องการผ่อนผันที่ต้องใช้วิจารณญาณอย่างนี้ Fontforge จะไม่สู่รู้ตัดสินใจให้ เราจึงต้องปรับเองด้วยมือ

จากภาพในตัวอย่างข้างต้น มีการเติมจุดกะระหว่างกลาง 4 จุดใน quadratic curve แต่เราสามารถลดจำนวนจุดกะนี้ลงได้ ไม่ว่าจะเพื่อความเรียบง่าย เพื่อลดขนาดข้อมูล (ซึ่งสำคัญสำหรับ web font) หรือเพื่อประสิทธิภาพในการ hint และการ rasterize ก็ตาม โดยแนวทางการลดจุดกะที่เป็นไปได้คือ:

  1. ตัดจุดกะด้วยมือ โดยเลือกจุดกะที่ต้องการตัดแล้วสั่ง Merge (Ctrl-M)
  2. ปรับ cubic curve ต้นทางด้วยมือให้สามารถประมาณได้ด้วยจำนวนจุดที่น้อยลง

ทั้งสองวิธีจะได้ quadratic curve ที่คลาดเคลื่อนจาก cubic curve เดิมเล็กน้อย แต่วิธีที่สองจะทำให้ได้ spline สองแบบที่ทาบกันสนิทกว่าแบบแรก เพราะมันถูกปรับไปด้วยกัน

ในฟอนต์ตัวแรก ๆ ที่ทำ ผมใช้วิธีแรก แต่ต่อมาก็ค่อย ๆ เกิดความคิดว่าวิธีที่สองน่าจะเหมาะกว่า และในที่สุดก็เลือกวิธีที่สองเป็นหลัก

แล้ว cubic curve แบบไหนที่จะใช้จำนวนจุดกะน้อยลง?

ก่อนอื่น คนที่เคย edit cubic curve จะรู้ว่าเราสามารถปรับแขนทั้งสองของโค้งได้โดยยังได้โค้งที่ใกล้เคียงกับโค้งเดิม ด้วยการเพิ่มความยาวของแขนข้างหนึ่ง และลดความยาวของแขนอีกข้างหนึ่ง

Cubic curve adjustment

แน่นอนว่าในทางคณิตศาสตร์แล้ว โค้งที่ปรับแล้วถือว่าไม่ใช่โค้งเดียวกับโค้งเดิม แต่ความคลาดเคลื่อนระหว่างโค้งทั้งสองยังอยู่ในขอบเขตที่ยอมรับได้ด้วยสายตามนุษย์ โดยเฉพาะถ้าปรับไม่มาก แต่ถ้าปรับมากเกินไปก็จะเริ่มสังเกตเห็นความแตกต่างเมื่อนำมาทาบกัน (ซึ่งในทาง design เราก็อาจจะยังยอมรับได้อยู่ดี)

สำหรับโค้งในตัวอย่างข้างต้น เมื่อปรับแล้ว copy ข้ามมา quadratic layer เรากลับได้ curve ที่ใช้จุดกะเพียงจุดเดียว จากเดิมที่ใช้ถึง 4 จุด

Quadratic curve of the adjusted cubic curve

ถามว่า cubic curve แบบไหนที่ใช้จุดกะน้อย? แรก ๆ ที่ลองผิดลองถูกน้ัน ผมอาศัย sense เป็นหลัก คือพยายามให้แขนทั้งสองข้างได้ดุลกัน แต่เมื่อทำไปก็เริ่มถามตัวเองถึงคุณสมบัติทางคณิตศาสตร์ที่ชัดเจนกว่าการใช้ sense ซึ่งในที่สุดก็ได้คำตอบที่กลับไปหาพื้นฐานทางคณิตศาสตร์ของ cubic และ quadratic curve นั่นเอง

จาก blog เดิม ผมได้กล่าวไว้ว่า quadratic curve ที่มีจุดควบคุม P0, P1 และ P2 สามารถแทนได้ด้วย cubic curve ที่สมมูลกันโดยมีจุดควบคุม P0, (P0/3 + 2P1/3), (2P1/3 + P2/3), และ P2

Equivalent cubic curve of a quadratic curve

เราสามารถพูดในทางกลับกันได้ว่า cubic curve ที่ว่านี้ เมื่อแปลงเป็น quadratic curve ก็จะใช้จุดควบคุม P0, P1 และ P2 ได้ทันทีโดยไม่ต้องเติมจุดกะ

ถือเป็นอุดมคติของการประมาณโค้ง ยิ่งเราปรับ cubic curve ให้เข้าใกล้อุดมคตินี้มากเท่าไร เมื่อแปลงเป็น quadratic ก็จะใช้จุดกะระหว่างกลางน้อยลงเท่านั้น

อุดมคติที่ว่านี้ มีคุณสมบัติที่เห็นได้จากเรขาคณิตก็คือ เส้นตรงที่เชื่อมระหว่างจุดควบคุมทั้งสองขนานกันกับเส้นตรงที่เชื่อมระหว่างจุดปลายทั้งสอง โดยถ้าความยาวของแขนควบคุมเท่ากับ 2/3 ของระยะไปยังจุดตัดของแขนควบคุมทั้งสองพอดี ก็จะไม่ต้องใช้จุดกะเพิ่มเลย แต่ถ้าไม่ใช่ก็ต้องมีจุดกะเพิ่ม

ฉะนั้น แนวทางโดยทั่วไปก็คือ พยายามเล็งให้ polygon ที่เชื่อมระหว่างจุดปลายและจุดควบคุมของ cubic curve กลายเป็นสี่เหลี่ยมคางหมูหรือใกล้เคียง ซึ่งโดยทั่วไปก็จะทำให้มีจุดกะเพิ่มไม่เกิน 1 จุด

การปรับอื่น ๆ

ในบางกรณี ก่อนที่จะได้ cubic curve ที่สามารถแทนด้วย quadratic curve ที่เติมจุดกะไม่เกิน 1 จุด ก็อาจจำเป็นต้องปรับจุดต่อโค้งต่าง ๆ เพิ่มตามจำเป็น เช่น

  • เติมจุดบิดโค้ง (inflection point) เพื่อแบ่งโค้งที่บิดเป็นรูปตัว S ออกเป็นสองส่วน เนื่องจาก quadratic curve ไม่สามารถบิดเป็นตัว S ได้เหมือน cubic curve
  • เติมจุดต่อโค้งในโค้งที่หักเลี้ยวไม่สมมาตร จนจำเป็นต้องเติมจุดกะมากกว่า 1 จุด เช่น ในฟอนต์ตัวเอียงที่โค้งเดิมกำหนดจุดต่อโค้งที่ extrema เท่านั้น

การเติมจุดเหล่านี้ หากพิจารณาเฉพาะฟอนต์ที่ใช้ cubic spline อาจดูไม่จำเป็น แต่การเติมจุดต่อโค้งนอกจากจะช่วยให้ใช้จุดกะน้อยเมื่อแปลงเป็น quadratic แล้ว ก็ยังมีผลดีต่อการควบคุมความหนาของเส้นหมึกสำหรับ cubic spline เองด้วย เช่น การมีจุดกำกับที่จุดบิดโค้งก็ย่อมเพิ่มโอกาสการ hint หรือตรึงตำแหน่งที่จุดบิดโค้ง แทนที่จะปล่อยให้โค้งลอยไปมาตามผลการขยับจุดปลายระหว่าง apply hint

แผนการต่อไป

ในฟอนต์ชุด Arundina ที่กำลังจะตัดออกรุ่นนี้ ผมได้ปรับ spline เฉพาะฟอนต์ Arundina Sans เท่านั้น โดยใช้วิธีแรก (ยุบจุดกะใน quadratic spline เท่านั้น) และ commit ไปแล้ว ส่วน Arundina Sans Mono ผมเริ่มใช้วิธีที่สอง แต่น่าเสียดายที่ข้อมูลสูญหายไปหมด จึงไม่ได้รวมมาในรุ่นใหม่นี้ แต่จะนำหลักการที่ได้นี้ไปใช้ปรับฟอนต์ชุด Fonts-TLWG ในลำดับต่อไป

ป้ายกำกับ: , ,

16 กันยายน 2562

Thanks

ขอขอบคุณ ท่านที่ได้ สนับสนุน งานพัฒนาซอฟต์แวร์เสรีของผมในช่วงที่ผ่านมาครับ

นับจาก ครั้งที่แล้ว ขอขอบคุณผู้สนับสนุนงานของผมดังนี้:

  • เดือนกุมภาพันธ์ 2562
    • คุณวิทยา ไตรสารวัฒนะ
  • เดือนสิงหาคม 2562
    • ผู้ไม่ประสงค์จะออกนาม 1 ท่าน

ขอให้ทั้งสองท่านประสบความสำเร็จในหน้าที่การงาน สุขภาพแข็งแรงครับ

ปีนี้อาจเป็นปีที่งานพัฒนาซอฟต์แวร์ของผมขาดช่วงไปบ้าง เนื่องจากรับงานสอนพิเศษนักเรียนอยู่ช่วงหนึ่ง แต่ก็พอสรุปงานตั้งแต่ต้นปีได้ดังนี้:

  • งานแปล
    • ระดมแปล Xfce เพื่อเตรียมพร้อมสำหรับ Xfce 4.14 ซึ่งก็ได้ออกรุ่นไปแล้วเมื่อ 12 สิงหาคมที่ผ่านมา
  • Fonts-Arundina (ยังไม่ release):
    • ตรวจสอบปัญหา build reproducibility ต่อ สุดท้ายพบว่าเป็นปัญหาของ FontForge ใน Debian ที่ยังอัปเดตไม่ครบสำหรับฟอนต์ PostScript จึงคอมเมนต์ไปใน Debian #774274 เพื่อขออัปเดต
    • ทยอยปรับ quadratic spline ในเลเยอร์ Quad ต่อ (ยังไม่เสร็จ งานนี้เป็นงานมาราธอน)
  • งานต้นน้ำ:
    • release gtk-im-libthai 0.2.2 เพื่อปล่อยสิ่งที่ค้างอยู่ใน repository ถึงเกือบ 8 ปี โดยสิ่งเปลี่ยนแปลงหลัก ๆ คือการกำจัดการใช้ GTK+ API ที่ deprecated
  • Debian packaging:
    • ย้ายไป debhelper level 12 พร้อมกับใช้ debhelper-compat dependency แทน debian/compat และแก้ปัญหาที่เกิดกับ dh_missing ใน level 12 นี้
    • ปรับโครงสร้าง Git repository ตาม DEP-14 ครบทุกแพกเกจในความดูแล (แต่ยังรออัปโหลดอยู่ 2 แพกเกจ)
    • ปรับแพกเกจที่สร้าง udeb โดยให้ dh_makeshlibs สแกนหา udeb โอยอัตโนมัติแทนการใช้ option --add-udeb สำหรับ debhelper รุ่น 12.3 ขึ้นไป
    • ตรวจสอบและตัดสิ่งที่เก่าเกินไปจนไม่จำเป็นสำหรับ Bullseye แล้ว
    • อัปเดตทั่วไป
  • Debian อื่น ๆ:
    • file Debian #934804 สำหรับ bsdmainutils เพื่อขอปรับข้อมูลวันหยุดของไทยเพิ่มเติมในคำสั่ง calendar อันเนื่องมาจากพระราชพิธีบรมราชาภิเษก
  • OpenStreetMap
    • ปรับข้อมูลแผนที่ในตัวเมืองขอนแก่น
    • เป็นวิทยากรฝึกอบรมการสร้างแผนที่ OSM ที่ Thailand ICT Camp 2019 (ชะอำ) ร่วมกับคุณ Mishari Muqbil
    • เริ่มทดลองเก็บข้อมูล Mapillary ในตัวเมืองขอนแก่นตามคำแนะนำของคุณ Mishari
    • ปรับข้อมูลแผนที่รายทางที่ชะอำ และแผนที่อุทยานสิ่งแวดล้อมนานาชาติสิรินธร
    • ปรับข้อมูลแผนที่บริเวณ ต.นาจอมเทียน อ.สัตหีบ จ.ชลบุรี
    • เริ่มทำแผนที่จุดรับขยะอันตรายในเขตเทศบาลนครขอนแก่น

ป้ายกำกับ: , , , ,

01 กรกฎาคม 2562

DTAC Leaked Net Data Problem

หลังจากเจอปัญหา DTAC เน็ตมือถือรั่วมานานพอควร คือการหักค่า net data ทั้ง ๆ ที่ผมปิด net data ตลอดเวลา และใช้เน็ตผ่าน Wi-Fi เท่านั้น เดือน มิ.ย. ที่ผ่านมาเลยเช็กตัวเลขจริงจัง พบว่าค่าเน็ตรั่วที่ผมจ่ายทั้งเดือนคือ 57.78 บาท ในขณะที่ค่าโทรผมใช้แค่ 21.25 บาท ผมจ่ายเงินไปฟรี ๆ เกือบสามเท่าของที่ใช้จริง!

เมื่อตรวจสอบปริมาณการใช้ net data จากแอนดรอยด์เอง กลับพบว่าปริมาณการใช้เน็ตทั้งเดือนคือ 0 ไบต์! แล้ว DTAC ตัดเงินผมจากอะไร?

คำอธิบายมีสองแนว

  1. comment หนึ่งใน Pantip อธิบายว่า เทคโนโลยี 4G ออกแบบมาให้ใช้ data ล้วน จึงเชื่อมต่อ data ตลอดเวลาที่เปิดเครื่อง แม้แต่การโทรก็ใช้ data ผ่าน VoLTE แต่เพื่อการติดต่อกับเครือข่าย 3G หรือ 2G ก็จะทำ Circuit Switched FallBack (CSFB) สำหรับการโทรหรือ SMS ได้ แต่สำหรับการเชื่อมต่อ 4G ปกติ ยังไงก็ปิด data ไม่ได้ทั้งหมด ยังต้องมีส่วนที่ใช้ maintain การเชื่อมต่ออยู่ดี
  2. DTAC อธิบายถึงสาเหตุอื่นที่ไม่เกี่ยวกับเทคโนโลยี 4G คือ
    • เมื่อ Wi-Fi สัญญาณอ่อนหรือช้าลง เครื่องจะสลับมาใช้สัญญาณ 3G/4G โดยอัตโนมัติเพื่อความต่อเนื่อง
    • บาง app เช่น passbook จำเป็นต้องใช้สัญญาณ 3G/4G สื่อสารกับเครือข่ายเพื่อยืนยันเบอร์ที่ใช้งาน
    • เมื่อเครื่องเข้าสู่ sleep mode จะสลับจากการจับสัญญาณ Wi-Fi มาเป็น 3G/4G อัตโนมัติ

กรณีของผม ผมเชื่อว่ามาจากข้อ 1 เพราะเริ่มสังเกตเห็นอาการเน็ตรั่วหลังจากที่ในพื้นที่มีสัญญาณ DTAC-Turbo และมือถือผมก็จับสัญญาณนี้ ในขณะที่เครื่องของอีกคนที่ใช้ DTAC เหมือนกันจับสัญญาณ VoLTE และไม่มีปัญหาเน็ตรั่ว

ฉะนั้น ผมจึงแก้ปัญหาด้วยการตั้งมือถือให้เชื่อมต่อกับเครือข่าย 3G เท่านั้น แทนที่จะเชื่อม 3G/4G อัตโนมัติ

อย่างไรก็ดี ปัญหาข้อ 2 ก็ยังอาจมีได้สำหรับเครือข่าย 3G ก็เลยสั่งปิดสัญญาณอินเทอร์เน็ตที่เครือข่ายไปเลย โดยสำหรับ DTAC ใช้เบอร์ดังนี้

  • ปิดสัญญาณอินเทอร์เน็ต กด *104*72#
  • เปิดสัญญาณอินเทอร์เน็ต กด *104*71#

จากที่ผมสังเกตเปรียบเทียบกับเครื่องของเพื่อนที่ไม่มีปัญหาเน็ตรั่วทั้งที่ใช้ 4G เหมือนกัน ซึ่งก็ควรต้องใช้ data ในการ maintain การเชื่อมต่อเหมือนกัน แต่ VoLTE กลับไม่มีปัญหาการตัดเงิน ในขณะที่เครื่องที่ใช้ DTAC-Turbo กลับมีปัญหา หรือจะเป็นปัญหาของ DTAC-Turbo?

ทั้งนี้ ก็ต้องพิจารณาด้วยว่าปัญหานี้ไม่ได้พบแค่กับ DTAC เท่านั้น แต่ทั้ง AIS และ True ต่างก็ดูจะมีปัญหานี้เช่นกัน และถ้าทางแก้คือการถอยกลับไป 3G ก็หมายความว่าถ้าไม่แก้ปัญหาการคิดค่าใช้งานตรงนี้ การขยับไป 4G หรือ 5G ของประเทศก็อาจเกิดแรงเสียดทานจากผู้ใช้ได้

ป้ายกำกับ: ,

hacker emblem