Type Char e Unisgned

[hamming_burst]

Salve, vorrei chiedere un parere.
Devo togliermi questo dubbio, che ho da un po'.

In rete si trovano risposte confusionarie, e pure sbagliate alle volte, quindi chiedo qua direttamente.

Il dubbio è il seguente
premessa: sono in Linux Kernel Space, quindi utilizzo i tipi interi del kernel (linux/types.h).

Quello che devo fare sono operazioni matematiche su stringhe di caratteri ASCII (in C ovviamente).

Se devo fare sottrazioni su un carattere per trasformarlo in un altro qual'è il tipo corretto da usare.

Esistendo i tipi:

- char
- signed char
- unsigned char

Quale tipo intero devo usare per fare le sottrazioni o addizione:

- u8 (signed 1 byte)
- s8 (unsigned 1 byte)

Essendo a discrezione del compilatore sciegliere se un "char" è signed o unsigned qual'è il giusto tipo da usare, pensando alla rappresentazione binaria non è cosa da poco.
Quello che voglio fare è non usare cast per trasformare un "char" in un unsigned per fare operazioni con u8 ma usare la sua rappresenzione corretta.

Il rischio è un trabocco in negativo o maggiore del range dei caratteri ASCII, se è maggiore faccio un modulo e non ho problemi (la funzione che utilizzo è adibita a fare un modulo con un valore fisso) ma se è negativo, per questo vorrei sapere qual'è il tipo giusto.

Spero sia chiaro il dubbio, è una cosa che mi crea alcuni dubbi e spero mi aiutiate.


Grazie a chi risponde

[Rggb1]

"ham_burst":premessa: sono in Linux Kernel Space, quindi utilizzo i tipi interi del kernel (linux/types.h).

Quello che devo fare sono operazioni matematiche su stringhe di caratteri ASCII (in C ovviamente).

Ovvero

C='A'+2;

Giusto?

"ham_burst":Se devo fare sottrazioni su un carattere per trasformarlo in un altro qual'è il tipo corretto da usare.

Senza segno, ovvero

unsigned char C;

o ancora meglio, se è in kernel

__u8 C;

"ham_burst":Essendo a discrezione del compilatore sciegliere se un "char" è signed o unsigned qual'è il giusto tipo da usare, pensando alla rappresentazione binaria non è cosa da poco.

"Ni". Non del compilatore - non proprio - semmai della piattaforma target. "man gcc" per dettagli.

"ham_burst":Quello che voglio fare è non usare cast per trasformare un "char" in un unsigned per fare operazioni con u8 ma usare la sua rappresenzione corretta.

Solo per curiosità: perché il typecast no? Particolare avversione?

"ham_burst":Il rischio è un trabocco in negativo o maggiore del range dei caratteri ASCII, se è maggiore faccio un modulo e non ho problemi (la funzione che utilizzo è adibita a fare un modulo con un valore fisso) ma se è negativo, per questo vorrei sapere qual'è il tipo giusto.

Però non c'è errore, e quindi puoi fare il modulo comunque.

__u8 dunno='C'-'A';

Qual è il problema per te se hai questo codice?

[hamming_burst]

Perfetto mi hai chiarito alcune cose.

l'ultimo punto:

u8 dunno = 'C' - 'A'

se mi confermi che i char sono definiti come unsigned char allora non mi crea nessuno problema.

ma se metto così:

u8 dunno = 'A' - 'C';

mi fa venire un dubbione, diventa negativo, ed è questo che non mi era chiaro essendo unsigned e i char negativi non esistono, qui c'è il "trabocco" che pensavo. Se è come un intero senza segno dovrebbe corrispondere al carattere 2 anche se risulta -2.

Non volevo utilizzare il typecasting per questione di pignoleria di tipi, è per un progetto di sistemi.

Ti posto il pezzo di codice così vedi cosa intendo con i dubbi e ti chiedo se puoi consigliarmi dove è meglio cambiare:

char* funzione(char* cip,char* chiav,uint dim_cip,u8 dim_ch,u8 min_char,u8 max_char){

	uint i = 0;
	u8 j = 0;
	u8 s;
	char* res = kmalloc(dim_cip*(sizeof(char)),GFP_KERNEL);

//ciclo sulla stringa "cip" applicando una funzione su ogni carattere per "trasformarlo"
	while(i<(dim_cip-1)){
		
		s = ( ( ( ((u8)cip[i]) - min_char ) + max_char) - ( ((u8)chiav[j]) - min_char) ) +min_char;

// la funzione può restituire caratteri maggiori di 127 quindi faccio il modulo 
		if(s>128){
			s = s%max_char;
		}

		res[i] = (char)s;
		
		i++;
//se la lunghezza di cip è maggiore della chiave fa una rotazione e riparte dall'inizio
		j = (j+1)%(dim_ch-1);
	
	}

	res[dim_cip-1]='\0';

	return res; 

}

Ho tolto alcune cose per rendere il pezzo di codice più breve, ho lasciato il pezzo di codice dubbio e i tipi.

char* cip 

-> può andare da 0 a inf caratteri (limite kmalloc)

uint dim_cip

-> dimensione cip, unsigned int

char* chiav 

-> da 0 a 32 caratteri

u8 dim_ch

-> dimensione chiave, unsigned int da 1 byte per i pochi caratteri

u8 min_char

-> limite inferiore riferito alla tabella ascii va da 0 a 127

u8 max_char

-> limite superiore da 0 a 127;

Condizioni:

- $0 <=$ min_char $<$ max_char $<= 127$
- min_char $>=$ chiave $<=$ max_char
- $32>=$ chiave $<= 126$ caratteri stampabili

Spero sia abbastanza chiaro cosa debba fare, praticamente applicare quel popò di somme e sottrazioni con TIPI corretti, senza avere trabocchi maggiori o minori di 0 o 127.
Se è possibile senza usare il typecast

[apatriarca]

Nel paragrafo 6.4.4.4 Character constants dello standard C capoverso 10 si legge:

An integer character constant has type int. The value of an integer character constant containing a single character that maps to a single-byte execution character is the numerical value of the representation of the mapped character interpreted as an integer. The value of an integer character constant containing more than one character (e.g., 'ab'), or containing a character or escape sequence that does not map to a single-byte execution character, is implementation-defined. If an integer character constant contains a single character or escape sequence, its value is the one that results when an object with type char whose value is that of the single character or escape sequence is converted to type int.

In base allo standard C, l'espressione 'C' - 'A' ha tipo int e valore -2.

Un discorso un po' diverso deve essere fatto invece quando si lavora con dei char. Il valore in questo caso dipende dalla scelta di usare signed char o unsigned char per rappresentare i caratteri. In effetti il tipo char ha il solo scopo di rappresentare dei caratteri in modo indipendente dalla codifica utilizzata e l'operazione di sottrazione, anche se ammessa dallo standard, non ha secondo me molto senso dal punto di vista semantico. In effetti quale dovrebbe essere a tuo parere il valore corretto di una espressione come a - b quando a e b sono caratteri? Il risultato dipenderà ovviamente dalla codifica usata, ma usando i char si è volutamente deciso di ignorare questo aspetto del carattere.

Nel tuo programma devi usare a mio parere degli interi con almeno 16bit. in modo da poter contenere tutte le differenze di due valori a 8bit. Inoltre nel tuo programma dai per scontato che la codifica utilizzata sia quella ASCII. Ma questo non è in generale vero (però potrebbe esserlo nel kernel di linux - non lo conosco).

Che cosa stai cercando esattamente di fare nella tua applicazione? Vedo diversi punti problematici nella tua applicazione come l'uso di % con numeri potenzialmente negativi. Ricordati che (-3)%2 = -1 e che non stai calcolando il modulo ma il resto della divisione. Inoltre credo che tu abbia scritto min_char invece di max_char alla fine dell'espressione per calcolare s.

[Rggb1]

"apatriarca":In base allo standard C, l'espressione 'C' - 'A' ha tipo int e valore -2.

Corretto. Ma l'assegnazione è ugualmente corretta, esempio:

unsigned char uc;
uc='A';
//...
uc=44;
//...

In effetti il tipo char ha il solo scopo di rappresentare dei caratteri in modo indipendente dalla codifica utilizzata

"Ni", anche qui. NON ha quel solo scopo: char, int, long sono tutti tipi interi, con segno e senza segno, però...

e l'operazione di sottrazione, anche se ammessa dallo standard, non ha secondo me molto senso dal punto di vista semantico.

però se si parla di "caratteri" hai perfettamente ragione.

In effetti quale dovrebbe essere a tuo parere il valore corretto di una espressione come a - b quando a e b sono caratteri? Il risultato dipenderà ovviamente dalla codifica usata

Giustissimo, vediamo se ora il codice di ham_burst ha qualche senso compiuto

Che cosa stai cercando esattamente di fare nella tua applicazione? Vedo diversi punti problematici...

Vedi sopra, mo' me lo studio un po'.

[hamming_burst]

Per la semantica del linguaggio le operazioni matematiche su dei caratteri alfabetici non ha senso, hai ragione. Ma tale funzione, per il progetto, usa proprio tale espediente per la loro codifica per "criptare" i dati.
L'applicazione è il "cifrario di Vigenere" modificato con un min_char e un max_char che si basa sulla tabella ASCII

La funzione che ho postato è la decodifica e quelle operazioni sono l'unica funzione che ho trovato facendo delle prove che fa corrispondere codifica con decodifica

Faccio un'assunzione per il tipo di codifica ASCII proprio perchè il progetto si basa su tale codifica, ASCII ISO 646.
Andando a vedere lo standard e la rappresentazione binaria, hai ragione è meglio usare un s16.


Sono qua proprio per capire se tali operazioni sono corrette (la codifica è corretta senza dubbi, è stata data dai docenti e da Vigenere in persona), cioè vorrei capire se le varie sottrazioni funziono solo perchè utilizzo tipi corretti per le operazioni ma sbagliati per i tipi dello standard.
Nella programmazione normale, in esercizi si fa un cast ad intero e via, ma vorrei essere corretto nella vera tipizzazione (sono fresco del corso di semantica, forse è per questo mi faccio tutti sti problemi)

Posto anche la codifica, così capite di cosa parlo:

s = (((((u8)parola[i])-min_char)+(((u8)chiav[j])-min_char))%max_char)+min_char;

		if(s>128){
			s = s%max_char;
		}

le altre parti sono uguali, pure qua i tipi non se sono corretti.

la funzione di codifica è questa senza dubbi (il modulo dell' if forse non serve, l'ho messo per i dubbi descritti sopra).

Comunque intanto grazie mille dell'aiuto

SP (solo per): ho letto dopo il messaggio di Rggb, le cose riportate qui sono da riferisi come risposta al messaggio di apatriarca

[Rggb1]

@ham_burst

Scusa ma vedo hai bisogno di una "ripulita" al codice. Due considerazioni:
- per chiarezza, se vuoi lavorare su 'u8' non usare un array di char
- usa una maschera bit e non l'operazione modulo per "contenere" il risultato nel boundary desiderato, ovvero

#define BITMASK 0x7F
//...
s&=BITMASK;

mi sembra più semplice.

PS. Come diceva anche apatriarca, se il risultato di una espressione è negativo e viene assegnato ad un unsigned char, potresti avere delle sorprese - nel senso che il risultato potrebbe essere differente da quello aspettato. Quindi devi controllare la situazione con "if (a>b)..." o anche "res=(a>b?a-b:b-a)" ecc.

[apatriarca]

Non capisco il senso di verificare che $s$ sia inferiore di $128$ e fare il modulo per max_char. Vediamo infatti quali sono i valori possibili di $s$.

Se $p$ è un carattere del messaggio, $k$ è un carattere della chiave, $m$ è il carattere minimo e $M$ quello massimo, allora
$s = (((p - m) + (k - m)) mod M) + m$
$p - m$ e $k - m$ sono compresi tra $0$ e $M - m$, per cui $((p - m) + (k - m))$ è compreso tra $0$ e $2(M - m)$. Il minimo di questa espressione è quindi $m$ e il massimo è $min (M - 1, 2(M - m)) + m$. Facendo quindi il modulo per $M$ quando $s > 128$ si ottiene un'espressione del massimo ancora più complicata. A me non sembra corretto. È infatti possibile ottenere valori al di fuori dell'intervallo $[m, M]$.

Secondo me il metodo corretto di implementare il cifrario di Vigenère è quello di usare $D = M - m + 1$ come valore per il modulo (suppongo che $M$ sia un valore utilizzabile), cioè
$s = (((p - m) + (k - m)) mod D) + m$
In questo caso infatti il massimo per $s$ sarebbe $min (M - m, 2(M - m)) + m = M$. Inoltre ogni valore nell'intervallo $[m, M]$ ha esattamente la stessa probabilità di essere presente nel risultato al variare di $p$ e $k$.

La decodifica a questo punto sarebbe
$p = (((s - m) - (k - m)) mod D) + m = ((s - m - k + m) mod D) + m = ((s - k) mod D) + m$
Per poter usare % nel codice devi però stare attento a non far venire un risultato negativo in $s - k$. Una soluzione potrebbe essere quella di riscriverla nella forma $s - k + D$. Infatti il minimo di $(s - k + D)$ è
$m - M + D = m - M + M - m + 1 = 1$.

Se char è unsigned, allora i risultati sono compresi nell'intervallo $[m, M]$ e inferiori di $2^7$, mentre i risultati intermedi possono arrivare al valore massimo di $2(M - m)$. Questo valore è sempre inferiore a $2^8$, essendo $M - m <= 2^7 - 1$. Se char fosse quindi unsigned in ogni caso, un u8 sarebbe sufficiente. Ma sfortunatamente non è questo il caso e un char potrebbe anche essere signed. Le considerazioni precedenti sono infatti valide anche per i signed char, ma un valore maggiore di $2^7$ non è rappresentabile da un s8 e i valori negativi non sono rappresentabili da un u8. Il consiglio è quindi di usare un s16 oppure semplicemente un int.

[hamming_burst]

Davvero molto interessante la tua analisi dell'algoritmo di cifratura.
Però devo contraddirti, sull'utilizzo di D. Anche se sicuramente è corretta la tua analisi, dove guardi un intervallo, se cambio il numero della classe del modulo l'algoritmo crea codifiche non corrispondenti a quelle date dal testo del progetto.
La codifica è quella data dal docente e non posso modificarla, quella che devo scrivere è la decodifica.

Le assunzioni che hai fatto te secondo cui (p-m)+(k-m) è compreso tra 0 e 2(M-m) è per le condizioni che ho scritto qualche post sopra, giusto?
Mi son dimenticato di scrivere una cosa abbastanza ovvia sopra, la parola p è compresa tra 32 e 126 (caratteri stampabili).

Per ricapitolare:

invece che usare una stringa di char, uso un array di s16.

percio così:

- parola e chiave -> s16[]
- min e max-> u8 (è sempre il secondo operando)
- risultato -> s16[]

Adesso che ho i tipi, la decodifica può risulatare con segno negativo o superiore (sono al punto di partenza), per quello che ho scritto sopra, non mi è permesso modificare la funzione. Io facevo il modulo proprio per far corrispondere i dati nel range dell'ASCII ( una bit mask dopo il tuo consiglio).

Comunque adesso i dubbi dell'argomento del post si sono dissipati, grazie mille

[Rggb1]

Secondo me potevi benissimo usare unsigned char, ma comunque in questo modo ti semplifichi il lavoro delle formule.
Rovescio della medaglia: devi "trattare" gli array se vuoi operazioni su stringhe, ad esempio per eseguire stampe.

PS. Ma perché usi i tipi derivati (types.h)? Visto il problema da te illustrato (cifrario) direi che è app-space, non kernel-space,e quindi dovrebbe essere indipendente ed usare tipi integrali come unsigned et al. Oppure stai costruendo un modulo mod_vigenere?

[hamming_burst]

Esattamente!
Un modulo del kernel Linux che gestisce due virtual device driver (char device), uno che se acceduto codifica l'altro decodifica. Con tutte le questioni di kernel space (concorrenza ecc)

Per farla semplice le parole da codificare e decodificare vengono passate da user_space con una write, la chiave , min e max vengono impostati all'inserimento del modulo come parametri, con la verifica delle varie condizioni (uso u8 in min e max per il type_check gratuito nell'inserimento del modulo per minori di 0 ecc).

[Rggb1]

Interessante... quando hai finito posta il risultato da qualche parte, magari commentando, o meglio una bella pagina web. E' per un esame? Decisamente un prof illuminato

Però scusa, usando array di integer (aka __s16) a questo punto dovrai fare delle routine di conversione ingresso e uscita... ok la pianto. Vai online quando hai fatto.

[apatriarca]

Capisco che devi seguire le indicazioni del tuo professore, ma ripeto, la tua codifica non è quella di Vigenère. Considera per esempio questo esempio in Python preso dalla pagina di wikipedia per codificare e poi decodificare usando il cifrario di Vigenère una successione di caratteri da 'a' a 'z':

def vigenere(key, plaintext):
    i = 0
    ciphertext = ''
    for char in plaintext.lower():
        if ord(char) >= ord('a') and ord(char) <= ord('z'):
            ciphertext += chr(((ord(char) - ord('a') + ord(key[i]) - ord('a')) % 26) + ord('a'))
            i = (i + 1) % len(key)
        else:
            ciphertext += char
    return ciphertext.upper()

e la decodifica:

def erenegiv(key, ciphertext):
    i = 0
    plaintext = ''
    for char in ciphertext.lower():
        if ord(char) >= ord('a') and ord(char) <= ord('z'):
            plaintext += chr((ord(char) - ord(key[i])) % 26 + ord('a')).lower()
            i = (i + 1) % len(key)
        else:
            plaintext += char
    return plaintext

Come puoi vedere il modulo usato è 26 come nella mia analisi. Se vuoi posso sempre mostrarti anche altri codice che fanno esattamente la stessa cosa visto che non credi alla matematica.

Il mio consiglio di usare degli interi con almeno a 16 bit si riferiva solo ed esclusivamente ai calcoli intermedi, il risultato è comunque sempre inferiore a 128 e quindi un char è più che sufficiente.

[Rggb1]

"apatriarca":Capisco che devi seguire le indicazioni del tuo professore, ma ripeto, la tua codifica non è quella di Vigenère. Considera per esempio questo esempio in Python preso dalla pagina di wikipedia per codificare e poi decodificare usando il cifrario di Vigenère una successione di caratteri da 'a' a 'z'

Python, eek! Non mi ero soffermato sul codice, avevo capito che la funzione di codifica era data già fatta, ma effettivamente...

"apatriarca":Come puoi vedere il modulo usato è 26 come nella mia analisi.

... è ovvio, il modulo è 26, per i 26 caratteri dell'alfabeto (numero caratteri cifrabili).

@ham_burst: o la funzione di cifratura l'hai codificata sbagliata, o te l'hanno data sbagliata, oppure è differente apposta, illuminaci.

[hamming_burst]

Intanto devo ringraziarvi delle tante risposte che mi avete dato

Questo algoritmo è un cifrario di Vigenere modificato, mi sembrava di averlo specificato in uno dei post a metà:

L'applicazione è il "cifrario di Vigenere" modificato con un min_char e un max_char che si basa sulla tabella ASCII

non credi alla matematica.

Mai mi permetterei di dissentire su un'analisi con una dimostrazione ben specificata (sempre che non esita un controesempio che dimostri il contrario, in generale)

Visto che hai fatto tutte le tue assunzioni sulla vera codifica di Vigenere che utilizza una cifratura polimorfica (se non sbaglio), questa che il docente ci ha dato si basa invece su tutta la tabella ASCII (meglio dire da 32 a 126, per via delle condizioni che avevo scritto).

Farò un esposto al docente se la codifica è sbagliata


EDIT:
Sopra ho detto un'inesattezza.
Se il cifrario di vigenerè si basa sull'albabeto quindi numero di lettere 1 to 26, su TUTTO l'alfabeto letterario.
L'algoritmo che si utilizza in questo caso (che si basa su vigenerè) nella codifica/decofica può essere da 0 a 127, ma per ogni codifica si avrà un limite inferiore sulla tabella ASCII data da min e un limite superiore dato da max.

[apatriarca]

La mia non si trattava di una dimostrazione, essendo in effetti il cifrario di Vigenère uguale alla mia espressione per definizione. Volevo solo mostrare come il comportamento della codifica del tuo professore fosse molto diverso da quello del cifrario di Vigenére, a partire dall'insieme dei valori di output possibili. Il messaggio codificato potrebbe infatti avere caratteri non compresi nell'intervallo [min_char, max_char]!
Il codice Python funziona in modo analogo al tuo, usando dei valori di min_char = 'a' e max_char = 'z'. E come modulo usa 'z' - 'a' + 1 = 26. La mia espressione era più generale, ma l'idea principale rimane comunque la stessa:
1. sottrarre min_char sia ai caratteri del messaggio che a quelli della chiave in modo da usare l'aritmetica modulare;
2. sommare i caratteri del messaggio a quelli della chiave;
3. fare il modulo in modo che i caratteri finali siano all'interno dell'intervallo voluto (usando quindi max_char - min_char + 1 come modulo);
4. sommare min_char.
Ho postato quel codice perché presente nella pagina di Wikipedia e quindi velocemente accessibile. Per trovarne uno in C avrei dovuto cercare un po' con Google.

[hamming_burst]

Ma daiiii

Ho letto il tuo ultimo post e mi hai illuminato, stasera mi andrò a leggere più attentamente il codice che ho scritto io e i tuoi esempi e il codice di esempio in pyton e mi sembra di aver trovato il mio errore. Provo a fare qualche test e poi vi dico se ho trovato il giusto algoritmo.

Grazie mille davvero ad entrambi

[hamming_burst]

Allora, metto il codice corretto:

Codifica, con correzioni suggeritemi.

u8* cod(u8* parola,u8* chiav,uint dim_pa,u8 dim_ch,u8 min_char,u8 max_char){

	uint i = 0;
	s16 s = 0;

	u8 max_lim = (max_char - min_char) +1;
	
	u8 j = 0;

	u8* res = kmalloc(dim_pa*(sizeof(char))+1,GFP_KERNEL);
	
	while(i<(dim_pa-1)){
		
		s = ((((((s16)parola[i])-min_char)+(((s16)chiav[j])-min_char)))%max_lim)+min_char;

		res[i] = (u8)s;

		i++;
		j = (j+1)%(dim_ch-1);

	}
	
	res[dim_pa-1]=0;

	return res;

}

Decodifica, con le corruzioni sul limite, ma la funzione di decodifica che dovrebbe essere quella inversa alla codifica, cioè con un "-" in mezzo fa risultare valori negativi.
Questa invece funziona, gli eventuali sforamenti oltre l'intervallo [min_char,max_char] lo correggo con un modulo sul limite.

u8* dec(u8* cript,u8* chiav,uint dim_cr,u8 dim_ch,u8 min_char,u8 max_char){

	uint i = 0;
	
	s16 s;

	u8 max_lim = (max_char - min_char) +1;
	u8 j = 0;

	u8* res = kmalloc(dim_cr*(sizeof(u8))+1,GFP_KERNEL);

	while(i<dim_cr-1){
		
		//s = ((((s16)cript[i])-(s16)chiav[j])%max_lim)+min_char; valori negativi
		
		s = ((((s16)cript[i])+max_lim)-((s16)chiav[j]))+min_char;
		
		if(s>max_char){
			s = s%max_lim;
		}
		
		res[i] = (u8)s;
		
		i++;
		j = (j+1)%(dim_ch-1);
	
	}

	res[dim_cr-1]=0;

	return res; 

}

Così funziona la decodifica, aspetto eventuali suggerimenti per dimostrare che tale funzione anche matematicamente è corretta.
Io ho applicato il principio di "classe di equivalenza" per trovare il minimo numero positivo della classe.