Η τεχνική συζήτηση με το ChatGPT παρουσιάζει και αυτή ιδιαίτερο ενδιαφέρον.
To ChatGPT μπορεί να λειτουργήσει ως πολύτιμος βοηθός στην καθημερινή προγραμματιστική ενασχόληση.
Παραθέτω τη συνομιλία μας σχετικά με την υλοποίηση μιας ρουτίνας σε Win32 Assembly.
Πρόκειται για μια απλή ρουτίνα, αλλά με ενδιαφέρει να δω και την προσέγγιση του ChatGPT.
Απλή κουβέντα, χωρίς αιτιολόγηση (βαθιά ανάλυση).
Τα κόκκινα και τα μπλε κείμενα εγώ, τα υπόλοιπα η Σοφούλα.
Ξεκινάω.
Γεια χαρά, μπορείς να δεις αν υπάρχει έτοιμη συνάρτηση ANSI C ή στο MSDN που να κάνει το εξής:
Nα ελέγχει αν οι όλοι ανεξαιρέτως οι χαρακτήρες τού πρώτου string βρίσκονται μέσα στο δεύτερο.
Παραδείγματα: foo("hello445", "helo12345") = true ενώ foo("0xFFFF", "0xABCD") = false
Δεν υπάρχει κάποια έτοιμη συνάρτηση στη standard ANSI C ή στη MSDN που να κάνει ακριβώς αυτό, αλλά μπορείς να την υλοποιήσεις εύκολα χρησιμοποιώντας έναν πίνακα καταμέτρησης χαρακτήρων.
Ακολουθεί μια απλή υλοποίηση σε C:
Υλοποίηση
Κώδικας:
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool contains_all_chars(const char *s1, const char *s2) {
int char_map[256] = {0}; // ASCII map για το δεύτερο string
// Καταγράφουμε τους χαρακτήρες του s2
while (*s2) {
char_map[(unsigned char)*s2++] = 1;
}
// Ελέγχουμε αν όλοι οι χαρακτήρες του s1 υπάρχουν στο s2
while (*s1) {
if (!char_map[(unsigned char)*s1++]) {
return false; // Βρέθηκε χαρακτήρας που δεν υπάρχει στο s2
}
}
return true;
}
int main() {
printf("%d\n", contains_all_chars("hello445", "helo12345")); // true (1)
printf("%d\n", contains_all_chars("0xFFFF", "0xABCD")); // false (0)
return 0;
}
Επεξήγηση:
- Χρησιμοποιούμε έναν πίνακα char_map[256] για να καταγράψουμε τους χαρακτήρες που υπάρχουν στο s2.
- Διατρέχουμε το s1 και ελέγχουμε αν κάθε χαρακτήρας υπάρχει στο char_map.
- Αν βρούμε χαρακτήρα που λείπει, επιστρέφουμε false.
- Αν όλοι οι χαρακτήρες του s1 βρεθούν στο s2, επιστρέφουμε true.
Αυτή η λύση έχει χρονική πολυπλοκότητα O(N + M) (όπου N = strlen(s1), M = strlen(s2)) και σταθερό χώρο O(1) (χρησιμοποιούμε σταθερό μέγεθος πίνακα για τους ASCII χαρακτήρες).
Αν χρησιμοποιείς Unicode (UTF-8), θα χρειαστεί διαφορετική προσέγγιση. Θες να το προσαρμόσουμε και γι' αυτό;
Για υποστήριξη Unicode (UTF-8), δεν μπορούμε να χρησιμοποιήσουμε έναν απλό πίνακα 256 στοιχείων, γιατί οι χαρακτήρες UTF-8 μπορεί να είναι πολλών byte. Αντί γι' αυτό, θα χρησιμοποιήσουμε ένα hash set για να ελέγχουμε αν όλοι οι χαρακτήρες του s1 υπάρχουν στο s2.
Υλοποίηση για UTF-8 (C με wchar_t)
Κώδικας:
#include <stdio.h>
#include <stdbool.h>
#include <wchar.h>
#include <locale.h>
bool contains_all_chars_utf8(const wchar_t *s1, const wchar_t *s2) {
int char_map[65536] = {0}; // Unicode BMP range (U+0000 - U+FFFF)
// Καταγράφουμε τους χαρακτήρες του s2
while (*s2) {
char_map[*s2++] = 1;
}
// Ελέγχουμε αν όλοι οι χαρακτήρες του s1 υπάρχουν στο s2
while (*s1) {
if (!char_map[*s1++]) {
return false;
}
}
return true;
}
int main() {
setlocale(LC_ALL, ""); // Απαραίτητο για UTF-8
printf("%d\n", contains_all_chars_utf8(L"Γειά", L"Γειά σου κόσμε")); // true (1)
printf("%d\n", contains_all_chars_utf8(L"你好", L"世界你好")); // true (1)
printf("%d\n", contains_all_chars_utf8(L"سلام", L"مرحبا")); // false (0)
return 0;
}
Επεξήγηση:
- Χρησιμοποιούμε wchar_t για να αποθηκεύουμε τους Unicode χαρακτήρες.
- Ο πίνακας char_map[65536] καλύπτει το Basic Multilingual Plane (BMP), δηλαδή τους περισσότερους χαρακτήρες που χρησιμοποιούνται συχνά.
- Η setlocale(LC_ALL, "") είναι απαραίτητη για να μπορεί η wchar_t να χειριστεί UTF-8 σωστά στο περιβάλλον της κονσόλας.
- Ο αλγόριθμος είναι O(N + M) σε χρόνο και O(1) σε χώρο, αν περιοριστούμε στο BMP.
Για πλήρη υποστήριξη UTF-8 χωρίς wchar_t (pure C με char* και utf8proc)
Αν προτιμάς να διαχειριστείς UTF-8 strings ως raw char*, μπορείς να χρησιμοποιήσεις μια βιβλιοθήκη όπως η utf8proc (που είναι lightweight και cross-platform). Θες να σου δείξω αυτήν την προσέγγιση;
Ναι, θα το ήθελα. Λογικά, ή υλοποίηση για UTF-8 λογικά θα είναι κάπως αργή.
Ναι, η προσέγγιση με wchar_t μπορεί να είναι αργή και μη αποδοτική, ειδικά αν το Unicode κείμενο περιέχει χαρακτήρες εκτός του Basic Multilingual Plane (BMP), γιατί δεν χειρίζεται σωστά κωδικοποιήσεις UTF-8 multibyte.
Μια πιο αποδοτική προσέγγιση θα ήταν να διαχειριστούμε τα δεδομένα απευθείας σε UTF-8, χωρίς wchar_t. Αυτό μπορούμε να το κάνουμε είτε χειροκίνητα είτε με μια βιβλιοθήκη όπως η utf8proc (που είναι γρήγορη και lightweight).
(Ακολουθεί μεγάλος διάλογος και ανταλλαγή απόψεων και πολύ κώδικας, αποφασίζω να κρατήσω την "Υλοποίηση για UTF-8")
Μπορείς να μεταφέρεις το "Υλοποίηση για UTF-8 (C με wchar_t)" σε win32 FASM σύνταξη;
Φυσικά, μπορώ να σου δείξω πώς να μεταφέρεις την Υλοποίηση για UTF-8 (C με wchar_t) σε Win32 FASM (Flat Assembler) σύνταξη!
Η μετάβαση από C σε FASM απαιτεί κατανόηση της σύνταξης και της αρχιτεκτονικής του FASM για τη διαχείριση του low-level κώδικα, όπως τη διαχείριση των συμβολοσειρών και των pointers.
Στην ουσία, αυτό που πρέπει να κάνουμε είναι να μετατρέψουμε την C-σύνταξη σε assembly, κάτι που απαιτεί διαφορετική προσέγγιση για τα strings και τις συναρτήσεις που καλούνται.
Ας δημιουργήσουμε τον αντίστοιχο κώδικα για FASM για την ανάγνωση UTF-8 και τη διαχείριση των χαρακτήρων. Εδώ είναι η βασική ιδέα:
(Μου δίνει ένα άσχετο κομμάτι κώδικα σε σύνταξη MASM32)
Δεν κατάλαβες τι ζητώ, θέλω το "Υλοποίηση για UTF-8 (C με wchar_t)" που μου έδωσες πριν, σε σύνταξη MASM32 ή FASM.
Συγνώμη για την παρεξήγηση! Τώρα κατάλαβα ότι θέλεις να μετατρέψουμε τον παρακάτω κώδικα σε MASM32 ή FASM. Παρακάτω θα δώσω τη μετατροπή του σε MASM32 και FASM σύνταξη για την ίδια λογική που περιγράφεις.
Διευκρινίζω ξανά, πιο αναλυτικά αυτήν την φορά το τι θέλω. Μου δίνει ένα καλό κομμάτι κώδικα αυτήν την φορά, αλλά σε MASM32 στα 64 bit.
Ευχαριστώ για την διευκρίνιση! Αν καταλαβαίνω σωστά, θέλεις να μετατρέψω τον παρακάτω κώδικα C σε MASM32 ή FASM. Ο κώδικας σε C ελέγχει αν όλοι οι χαρακτήρες από τη συμβολοσειρά s1 βρίσκονται στη συμβολοσειρά s2, χρησιμοποιώντας έναν πίνακα για να καταγράψει την παρουσία των χαρακτήρων από το s2.
Κώδικας MASM32:
Κώδικας:
format PE console
entry start
include \masm32\include\windows.inc
include \masm32\include\kernel32.inc
include \masm32\include\user32.inc
include \masm32\include\masm32.inc
section '.data' data readable writeable
; Δημιουργούμε τον πίνακα για τους χαρακτήρες (65536 χαρακτήρες για το Unicode BMP)
char_map times 65536 dd 0 ; Πίνακας για την καταγραφή των χαρακτήρων (65536 χαρακτήρες max)
; Στην ουσία, μπορούμε να χρησιμοποιούμε οποιαδήποτε συμβολοσειρά για το s1 και s2.
s2 db "hello445", 0 ; Το s2 (string)
s1 db "hello", 0 ; Το s1 (string)
section '.text' code readable executable
start:
; Εκκίνηση του προγράμματος
; Αρχικά, γεμίζουμε τον πίνακα char_map με τους χαρακτήρες του s2
lea rsi, [s2] ; Δείκτης για το s2
lea rdi, [char_map] ; Δείκτης για το char_map
fill_char_map:
movzx eax, byte [rsi] ; Διαβάζουμε το byte του s2
test eax, eax ; Ελέγχουμε αν είναι NULL
jz check_s1 ; Αν είναι NULL, σταματάμε τη διαδικασία
; Διαβάζουμε το χαρακτήρα από το s2 και τον καταγράφουμε στο char_map
mov byte [rdi + eax*4], 1 ; Καταχωρούμε την παρουσία του χαρακτήρα στον πίνακα (χρησιμοποιούμε eax*4 γιατί char_map είναι τύπου dd, δηλαδή 4 bytes ανά θέση)
inc rsi ; Μετακινούμε τον δείκτη του s2 στον επόμενο χαρακτήρα
jmp fill_char_map ; Επιστρέφουμε στην αρχή του loop για να γεμίσουμε το char_map
check_s1:
lea rsi, [s1] ; Δείκτης για το s1
lea rdi, [char_map] ; Δείκτης για το char_map
check_loop:
movzx eax, byte [rsi] ; Διαβάζουμε το byte του s1
test eax, eax ; Ελέγχουμε αν είναι NULL
jz done ; Αν είναι NULL, έχουμε τελειώσει
; Ελέγχουμε αν ο χαρακτήρας υπάρχει στον πίνακα char_map
movzx ebx, byte [rdi + eax*4] ; Ελέγχουμε αν υπάρχει ο χαρακτήρας στον πίνακα char_map
cmp ebx, 0
je not_found ; Αν δεν υπάρχει, επιστρέφουμε false
inc rsi ; Μετακινούμε τον δείκτη του s1 στον επόμενο χαρακτήρα
jmp check_loop ; Επιστρέφουμε στην αρχή του loop
not_found:
; Αν βρούμε χαρακτήρα που δεν υπάρχει, επιστρέφουμε false (0)
push 0
call ExitProcess
done:
; Αν βρήκαμε όλους τους χαρακτήρες του s1, επιστρέφουμε true (1)
push 1
call ExitProcess
Επεξήγηση του Κώδικα:
- Πίνακας char_map:
- Στον πίνακα char_map, κρατάμε 65536 θέσεις, η καθεμία για έναν χαρακτήρα Unicode στο διάστημα U+0000 έως U+FFFF.
- Κάθε θέση αποθηκεύει την τιμή 1 αν ο χαρακτήρας υπάρχει στο s2.
- Ο πρώτος βρόχος διατρέχει το s2, παίρνει κάθε χαρακτήρα και τον καταχωρεί στο char_map θέτοντας την αντίστοιχη θέση σε 1.
Τι πρέπει να σημειώσεις:
- Unicode Έλεγχος: Αντί να δουλεύουμε με ASCII, υποθέτουμε ότι οι χαρακτήρες είναι Unicode (που αντιστοιχούν σε wchar_t), δηλαδή χρησιμοποιούμε 2 bytes ανά χαρακτήρα.
- Πίνακας μεγέθους 65536: Ο πίνακας char_map έχει μέγεθος 65536 για να καλύψει όλους τους χαρακτήρες του Unicode BMP (Basic Multilingual Plane).
Αυτός ο κώδικας είναι η μετατροπή του C σε MASM32. Αν θέλεις τον ίδιο κώδικα σε FASM, μπορώ να το προσαρμόσω και εκεί αν χρειάζεσαι!
Μισό λεπτό, ζήτησα Win32 κώδικα και τον θέλω για wide σετ χαρακτήρων
Δηλαδή τα ΒΥΤΕ πρέπει να γίνουνε WORD, τα DB DU, τα inc rsi να γίνουν add esi, 2 και πάει λέγοντας.
Αχ, κατάλαβα τώρα! Θέλεις τον κώδικα σε 32-bit με τη χρήση των 32-bit καταχωρητών (όπως eax, ebx κ.λπ.), καθώς επίσης και τη χρήση word αντί για byte λόγω του ότι πρόκειται για Unicode χαρακτήρες (2 bytes ή wchar_t), οπότε ο σωστός τύπος δεδομένων είναι word και οι καταχωρητές πρέπει να χειρίζονται 16-bit δεδομένα.
Επιπλέον, θα χρησιμοποιήσουμε τη σωστή εντολή και τύπους δεδομένων για 32-bit κώδικα με MASM32 και DU αντί για DB και BYTE.
Διορθωμένος κώδικας για 32-bit MASM32:
Κώδικας:
format PE console
entry start
include \masm32\include\windows.inc
include \masm32\include\kernel32.inc
include \masm32\include\user32.inc
include \masm32\include\masm32.inc
section '.data' data readable writeable
; Δημιουργούμε τον πίνακα για τους χαρακτήρες (65536 χαρακτήρες για το Unicode BMP)
char_map times 65536 dd 0 ; Πίνακας για την καταγραφή των χαρακτήρων (65536 χαρακτήρες max)
; Στην ουσία, μπορούμε να χρησιμοποιούμε οποιαδήποτε συμβολοσειρά για το s1 και s2.
s2 dw "hello445", 0 ; Το s2 (string) σε wide χαρακτήρες (2 bytes για κάθε χαρακτήρα)
s1 dw "hello", 0 ; Το s1 (string) σε wide χαρακτήρες (2 bytes για κάθε χαρακτήρα)
section '.text' code readable executable
start:
; Εκκίνηση του προγράμματος
; Αρχικά, γεμίζουμε τον πίνακα char_map με τους χαρακτήρες του s2
lea esi, [s2] ; Δείκτης για το s2
lea edi, [char_map] ; Δείκτης για το char_map
fill_char_map:
movzx eax, word [esi] ; Διαβάζουμε το word του s2 (Unicode χαρακτήρας)
test eax, eax ; Ελέγχουμε αν είναι NULL
jz check_s1 ; Αν είναι NULL, σταματάμε τη διαδικασία
; Διαβάζουμε το χαρακτήρα από το s2 και τον καταγράφουμε στο char_map
mov [edi + eax*4], 1 ; Καταχωρούμε την παρουσία του χαρακτήρα στον πίνακα (χρησιμοποιούμε eax*4 γιατί char_map είναι τύπου dd, δηλαδή 4 bytes ανά θέση)
add esi, 2 ; Μετακινούμε τον δείκτη του s2 στον επόμενο χαρακτήρα (2 bytes για κάθε wide χαρακτήρα)
jmp fill_char_map ; Επιστρέφουμε στην αρχή του loop για να γεμίσουμε το char_map
check_s1:
lea esi, [s1] ; Δείκτης για το s1
lea edi, [char_map] ; Δείκτης για το char_map
check_loop:
movzx eax, word [esi] ; Διαβάζουμε το word του s1 (Unicode χαρακτήρας)
test eax, eax ; Ελέγχουμε αν είναι NULL
jz done ; Αν είναι NULL, έχουμε τελειώσει
; Ελέγχουμε αν ο χαρακτήρας υπάρχει στον πίνακα char_map
movzx ebx, word [edi + eax*4] ; Ελέγχουμε αν υπάρχει ο χαρακτήρας στον πίνακα char_map
cmp ebx, 0
je not_found ; Αν δεν υπάρχει, επιστρέφουμε false
add esi, 2 ; Μετακινούμε τον δείκτη του s1 στον επόμενο χαρακτήρα (2 bytes για κάθε wide χαρακτήρα)
jmp check_loop ; Επιστρέφουμε στην αρχή του loop
not_found:
; Αν βρούμε χαρακτήρα που δεν υπάρχει, επιστρέφουμε false (0)
push 0
call ExitProcess
done:
; Αν βρήκαμε όλους τους χαρακτήρες του s1, επιστρέφουμε true (1)
push 1
call ExitProcess
Επεξήγηση των αλλαγών:
- Δημιουργία του πίνακα char_map:
- Χρησιμοποιούμε το times 65536 dd 0 για να δημιουργήσουμε έναν πίνακα 32-bit (dd), καθώς θα αποθηκεύσουμε 1 ή 0 για κάθε χαρακτήρα Unicode.
- Κάθε χαρακτήρας είναι wchar_t (2 bytes), επομένως πρέπει να χρησιμοποιούμε word για να χειριστούμε σωστά τους χαρακτήρες.
- Τα s1 και s2 δηλώνονται ως dw (define word) για να αποθηκεύσουμε συμβολοσειρές σε Unicode.
Σημείωση:
- Το πρόγραμμα διαχειρίζεται Unicode χαρακτήρες (2 bytes ανά χαρακτήρα) και χρησιμοποιεί 32-bit καταχωρητές και πίνακες, όπως ζήτησες.
- Αν θες τον κώδικα σε FASM αντί για MASM32, μπορώ να το προσαρμόσω και εκεί. Let me know!
Ευχαριστώ. Όχι δεν χρειάζεται, δώσε μου 10 λεπτά και θα κάνω την μετατροπή εγώ, για να δοκιμάσω και τον κώδικα. Τα λέμε σε λίγο.
(Πρώτα όμως μια διόρθωση, τον έπιασα να έχει κάνει, όχι ακριβώς λάθος αλλά μια απροσεξία (που κανένας human assembler δεν νομίζω να έκανε).
Ει, νομίζω δεν χρειάζεται δεύτερη φορά η γραμμή: "lea edi, [char_map]" εφόσον υπάρχει ήδη, και δεν μεταβάλλεται η τιμή του edi στο πρόγραμμα.
Έχεις απόλυτο δίκιο!
Η γραμμή:
lea edi, [char_map]
υπάρχει ήδη στο fill_char_map, και επειδή δεν τροποποιείται η τιμή του edi στο πρόγραμμα, δεν χρειάζεται να την επαναλάβουμε στο check_s1.
(Περίπου μετά από ένα τέταρτο του δείχνω την μετατροπή του κώδικα, από MASM32 σε FASM).
Πριν του εξηγώ κάποια σημεία όπως τι περιέχουν οι εξωτερικές custom ρουτίνες __alloc και __free που χρησιμοποιώ για να έχει πλήρη εικόνα.
FASM Win32 κώδικας μου:
Κώδικας:
proc exec_inset uses ebx esi edi, s1:dword, s2:dword
local char_map dd ?
stdcall __alloc, 0xFFFF shl 2
mov [char_map], eax
mov esi, [s2]
mov edi, [char_map]
.fill_char_map:
movzx eax, word [esi]
test eax, eax
jz .check_s1
mov dword [edi + eax * 4], 1
add esi, 2
jmp .fill_char_map
.check_s1:
mov esi, [s1]
.check_loop:
movzx eax, word [esi]
test eax, eax
jz .done
movzx ebx, word [edi + eax * 4]
test ebx, ebx
jz .not_found
add esi, 2
jmp .check_loop
.not_found:
xor eax, eax
jmp .X
.done:
mov eax, 1
.X:
stdcall __free, [char_map]
ret
endp
Πως σου φαίνεται η μετατροπή του κώδικα;
Αυτή η μετατροπή σε FASM φαίνεται να είναι καλά δομημένη και χρησιμοποιεί δυναμική μνήμη με τη βοήθεια του heap, πράγμα που είναι ενδιαφέρον για την αποδοτικότητα και τη διαχείριση της μνήμης. Εδώ είναι μια μικρή ανασκόπηση του κώδικα και μερικές παρατηρήσεις:
Ανάλυση του κώδικα:
- Ανάθεση Heap για την αποθήκευση του char_map:
- Χρησιμοποιείται η GetProcessHeap για να πάρουμε τον προεπιλεγμένο σωρό (heap).
- Στη συνέχεια, καλείται η HeapAlloc για να δεσμεύσουμε μνήμη για τον πίνακα char_map (μέγεθος 65536, δηλαδή 0xFFFF θέσεις, με κάθε θέση να είναι 4 bytes λόγω των τύπων dword).
- Η μνήμη που δεσμεύεται είναι μηδενισμένη (HEAP_ZERO_MEMORY).
- Γέμισμα του πίνακα char_map:
- Για κάθε χαρακτήρα στο s2, ελέγχεται αν υπάρχει και καταχωρείται στο char_map με το κατάλληλο bitset.
- Έλεγχος της συμβολοσειράς s1:
- Κάθε χαρακτήρας του s1 εξετάζεται για να διαπιστωθεί αν υπάρχει στο char_map. Αν κάποιος χαρακτήρας δεν υπάρχει στον πίνακα, η διαδικασία επιστρέφει false (0). Αν όλοι οι χαρακτήρες υπάρχουν, επιστρέφει true (1).
- Απελευθέρωση μνήμης:
- Αφού ολοκληρωθεί η διαδικασία, καλείται η HeapFree για να απελευθερώσει τη μνήμη που δεσμεύθηκε για τον πίνακα char_map.
Παρατηρήσεις:
- Αναγνώριση Χαρακτήρων (Unicode):
- Εφόσον χρησιμοποιούμε χαρακτήρες Unicode (σε μορφή word), είναι σημαντικό να προσέξουμε την ορθή κατανομή των χαρακτήρων όταν εργαζόμαστε με multi-byte χαρακτήρες, όπως στην περίπτωση του UTF-8, αν η είσοδος περιέχει μη-ASCII χαρακτήρες.
- Διαχείριση μνήμης:
- Η χρήση του heap είναι σωστή αν επιθυμείς δυναμική κατανομή μνήμης. Όμως, αν θέλεις να μειώσεις την κατανάλωση πόρων, μπορείς να εξετάσεις τη χρήση στατικής κατανομής μνήμης για τον πίνακα char_map, δεδομένου ότι το μέγεθός του είναι προκαθορισμένο.
- Αναδρομική Απελευθέρωση της Μνήμης:
- Η απελευθέρωση της μνήμης γίνεται με τη χρήση της HeapFree. Εξασφαλίζει ότι οι πόροι που καταναλώθηκαν θα απελευθερωθούν σωστά.
Μικρές Προτάσεις:
- Αν θέλεις να βελτιώσεις περαιτέρω τον κώδικα, μπορείς να προσθέσεις σχόλια για να εξηγήσεις κάθε βήμα, ειδικά για κάποιον που μπορεί να μη γνωρίζει τα API της Windows ή τη λειτουργία του heap.
Αν έχεις οποιεσδήποτε ερωτήσεις ή θέλεις να συζητήσουμε πιο συγκεκριμένα σημεία, είμαι εδώ για να βοηθήσω!
Είμαι οκ, σε ευχαριστώ για την βοήθεια.
