Category Archives: Source Code

An implementation of the algorithm “DES” written in Java.

The algorithms described in this standard specifies both enciphering and deciphering operations which are based on a binary number called a key.

A DES key consists of 64 binary digits (“0″s or “1”s) of which 56 bits are randomly generated and used directly by the algorithm. The other 8 bits, which are not used by the algorithm, may be used for error detection. The 8 error detecting bits are set to make the parity of each 8-bit byte of the key odd, i.e., there is an odd number of “1”s in each 8-bit byte1. A TDEA key consists of three DES keys, which is also referred to as a key bundle. Authorized users of encrypted computer data must have the key that was used to encipher the data in order to decrypt it. The encryption algorithms specified in this standard are commonly known among those using the standard. The cryptographic security of the data depends on the security provided for the key used to encipher and decipher the data.

Data can be recovered from cipher only by using exactly the same key used to encipher it. Unauthorized recipients of the cipher who know the algorithm but do not have the correct key cannot derive the original data algorithmically. However, it may be feasible to determine the key by a brute force “exhaustion attack.” Also, anyone who does have the key and the algorithm can easily decipher the cipher and obtain the original data. A standard algorithm based on a secure key thus provides a basis for exchanging encrypted computer data by issuing the key used to encipher it to those authorized to have the data.

For more details, see this document.

This is the main written in java:
</pre>
import java.io.UTFDataFormatException;
import java.nio.charset.Charset;
/**
 *
 * @author Paolo Musolino
 */
public class EsameCrittografia {

&nbsp;

private static final Charset UTF8_CHARSET = Charset.forName("UTF-8");
 /**
 * @param args
 */
 public static void main(String[] args) {


 try{


 String testoInChiaro = "questo è l'algoritmo des";

 //DES
 String k = "5qw8sd4h";

 System.out.println("Testo in chiaro: "+testoInChiaro);

 byte[] enc = DES.encrypt(testoInChiaro.getBytes(), k.getBytes());
 System.out.println("Testo criptato con DES: "+new String(enc));

byte[] dec = DES.decrypt(enc, k.getBytes());
 System.out.println("Testo decriptato con DES: "+new String(dec));
 System.out.println("------------------");



}catch(Exception e){
 e.printStackTrace();
 }
 }

}
<pre>

This is the Java class that contains the operation of the des (comments are written in Italian):

</pre>
/**
 *
 * @author pmusolino
 */
public class DES {
 // tabella di permutazione iniziale
 private static int[] IP = { 58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36,
 28, 20, 12, 4, 62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32,
 24, 16, 8, 57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19,
 11, 3, 61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7 };
 // tabella di permutazione finale
 private static int[] invIP = { 40, 8, 48, 16, 56, 24, 64, 32, 39, 7, 47,
 15, 55, 23, 63, 31, 38, 6, 46, 14, 54, 22, 62, 30, 37, 5, 45, 13,
 53, 21, 61, 29, 36, 4, 44, 12, 52, 20, 60, 28, 35, 3, 43, 11, 51,
 19, 59, 27, 34, 2, 42, 10, 50, 18, 58, 26, 33, 1, 41, 9, 49, 17,
 57, 25 };
 // Permutazione P (nel metodo f(Feistel))
 private static int[] P = { 16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5,
 18, 31, 10, 2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4,
 25

};
 // chiave di permutazione iniziale 64 bit => 56 bit
 private static int[] PC1 = { 57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34,
 26, 18, 10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36, 63,
 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22, 14, 6, 61, 53,
 45, 37, 29, 21, 13, 5, 28, 20, 12, 4 };
 // chiave di permutazione al round i 56 => 48
 private static int[] PC2 = { 14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10,
 23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2, 41, 52, 31, 37, 47, 55,
 30, 40, 51, 45, 33, 48, 44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29,
 32 };
 // shift della chiave per ogni round
 private static int[] keyShift = { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2,
 2, 1 };
 // tabella di permutazione per l'espansione nella funzione di feistel
 private static int[] expandTbl = { 32, 1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9, 8,
 9, 10, 11, 12, 13, 12, 13, 14, 15, 16, 17, 16, 17, 18, 19, 20, 21,
 20, 21, 22, 23, 24, 25, 24, 25, 26, 27, 28, 29, 28, 29, 30, 31, 32,
 1 };

 // scatola di sostituzione s-box
 private static int[][][] sboxes = {
 { { 14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7 },
 { 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8 },
 { 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0 },
 { 15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13 }
 },
 { { 15, 1, 8, 14, 6, 11, 3, 2, 9, 7, 2, 13, 12, 0, 5, 10 },
 { 3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5 },
 { 0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15 },
 { 13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9 }
 },
 { { 10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8 },
 { 13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1 },
 { 13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7 },
 { 1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12 }
 },
 { { 7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15 },
 { 13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9 },
 { 10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4 },
 { 3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14 }
 },
 { { 2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9 },
 { 14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6 },
 { 4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14 },
 { 11, 8, 12, 7, 1, 14, 2, 12, 6, 15, 0, 9, 10, 4, 5, 3 }
 },
 { { 12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11 },
 { 10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8 },
 { 9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6 },
 { 4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13 }

},
 { { 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1 },
 { 13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6 },
 { 1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2 },
 { 6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12 }

},
 { { 13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7 },
 { 1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2 },
 { 7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8 },
 { 2, 1, 14, 7, 4, 10, 18, 13, 15, 12, 9, 0, 3, 5, 6, 11 }

} };

// contiene le subkeys
 private static byte[][] K;

&nbsp;

//setta i bit all'interno dell'array di byte che gli passiamo con val nella posizione prestabilita
 private static void setBit(byte[] data, int pos, int val) {
 int posByte = pos / 8;
 int posBit = pos % 8;
 byte tmpB = data[posByte];
 tmpB = (byte) (((0xFF7F >> posBit) & tmpB) & 0x00FF);
 byte newByte = (byte) ((val << (8 - (posBit + 1))) | tmpB);
 data[posByte] = newByte;
 }

//funzione che estrae un bit (singolo) da un array di byte.
 private static int extractBit(byte[] data, int pos) {
 int posByte = pos / 8;
 int posBit = pos % 8;
 byte tmpB = data[posByte];
 int bit = tmpB >> (8 - (posBit + 1)) & 0x0001;
 return bit;
 }

//rotazione verso sinistra, di uno o due bit.
 //Questa funzione viene richiamata nella generazione delle chiavi.
 //entrambe le metà vengono fatte slittare verso sinistra di 1 o 2 bit
 // (per i round 1, 2, 9, 16 lo shift, cioè lo slittamento, è di 1 bit, per gli altri è di 2)
 private static byte[] rotLeft(byte[] input, int len, int pas) {
 int nrBytes = (len - 1) / 8 + 1;
 byte[] out = new byte[nrBytes];
 for (int i = 0; i < len; i++) {
 int val = extractBit(input, (i + pas) % len);
 setBit(out, i, val);
 }
 return out;
 }

//questo metodo estrae i bit dividendo il testo in chiaro da 64 bit in due metà, richiamata in encrypt64Bloc
 private static byte[] extractBits(byte[] input, int pos, int n) {
 int numOfBytes = (n - 1) / 8 + 1;
 byte[] out = new byte[numOfBytes];
 for (int i = 0; i < n; i++) {
 int val = extractBit(input, pos + i);
 setBit(out, i, val);
 }
 return out;

}


 //permuta i byte in input con quelli presente su una delle tavole (esempio: IP, inv IP)
 private static byte[] permutFunc(byte[] input, int[] table) {
 int nrBytes = (table.length - 1) / 8 + 1;
 byte[] out = new byte[nrBytes];
 for (int i = 0; i < table.length; i++) {
 int val = extractBit(input, table[i] - 1);
 setBit(out, i, val);
 }
 return out;

}

 //funzione che permette lo xor dei bit, ed è utilizzato per esempio nel terzo passaggio del DES
 //poiché ai 48 bit dell'espansione viene applicato un or esclusivo con la chiave
 //di ciclo a 48 bit.
 private static byte[] xor_func(byte[] a, byte[] b) {
 byte[] out = new byte[a.length];
 for (int i = 0; i < a.length; i++) {
 out[i] = (byte) (a[i] ^ b[i]);
 }
 return out;

}

 /*
 * E' la funzione che cripta realmente, quella che elabora blocchi da 64 bit,
 * che divide il blocco in due parti uguali da 32 bit, e che esegue tutte le operazioni (richiamando
 * le altre funzioni).
 * Il risultato viene poi utilizzato in "encrypt" che compatta tutto il testo in chiaro in blocchi
 * maggiori di 64 bit (se più lungo ovviamente).
 */
 private static byte[] encrypt64Bloc(byte[] bloc,byte[][] subkeys, boolean isDecrypt) {
 byte[] tmp = new byte[bloc.length];
 byte[] R = new byte[bloc.length / 2];
 byte[] L = new byte[bloc.length / 2];

tmp = permutFunc(bloc, IP);

L = extractBits(tmp, 0, IP.length/2);
 R = extractBits(tmp, IP.length/2, IP.length/2);

for (int i = 0; i < 16; i++) {
 byte[] tmpR = R;
 if(isDecrypt)
 R = f_func(R, subkeys[15-i]);
 else
 R = f_func(R,subkeys[i]);
 R = xor_func(L, R);
 L = tmpR;
 }

tmp = concatBits(R, IP.length/2, L, IP.length/2);

tmp = permutFunc(tmp, invIP);
 return tmp;
 }

/* La funzione Feistel, opera su mezzo blocco (32 bit) per volta e consiste di 4 passi.
 1. Espansione - il mezzo blocco di 32 bit è espanso fino a 48 bit utilizzando la permutazione
 di espansione che duplica alcuni bit.
 2. Miscelazione con la chiave - il risultato è combinato con una sottochiave usando
 * un'operazione di XOR. Sedici sottochiavi di 48 bit — una per ogni ciclo —
 * sono derivate dalla chiave principale usando il gestore della chiave (descritto più avanti
 * nella funzione generateSubKeys).
 3- Sostituzione - dopo la miscelazione con la sottochiave, il blocco viene diviso in 8 parti
 * di 6 bit prima del processamento con le S-box.
 * Ognuna delle 8 S-box sostituisce 6 bit in input con 4 bit in output mediante una trasformazione
 * non lineare effettuata mediante una tabella. Le S-box forniscono il cuore della sicurezza del DES
 * — senza di esse, la cifratura sarebbe lineare e quindi facilmente violabile.
 * Permutazione - infine, i 32 bit risultanti dalle S-box sono riordinati in base alle permutazioni
 * fisse della Permutation-box.
 4. L'alternanza di sostituzioni mediante le S-box, le permutazioni con la P-box
 * e le espansioni forniscono la cosiddetta confusione e diffusione,
 * (concetto identificato da Claude Shannon negli anni '40) come condizione necessaria
 * per rendere pratica e sicura la cifratura.
 */
 private static byte[] f_func(byte[] R, byte[] K) {
 byte[] tmp;
 tmp = permutFunc(R, expandTbl);
 tmp = xor_func(tmp, K);
 tmp = s_func(tmp);
 tmp = permutFunc(tmp, P);
 return tmp;
 }

/*
 * Utilizzata nel 4° passaggio di ogni round del DES .
 * Il risultato dello XOR del 3° passaggio viene utilizzato
 * nella S-box (sboxes). Il risultato è una parola di 32 bit.
 */
 private static byte[] s_func(byte[] in) {
 in = separateBytes(in, 6);
 byte[] out = new byte[in.length / 2];
 int halfByte = 0;
 for (int b = 0; b < in.length; b++) {
 byte valByte = in[b];
 int r = 2 * (valByte >> 7 & 0x0001) + (valByte >> 2 & 0x0001);
 int c = valByte >> 3 & 0x000F;
 int val = sboxes[b][r];
 if (b % 2 == 0)
 halfByte = val;
 else
 out[b / 2] = (byte) (16 * halfByte + val);
 }
 return out;
 }


 // dopo la miscelazione con la sottochiave, il blocco viene diviso in 8 parti di 6 bit.
 //Viene utilizzata nella s_func.
 private static byte[] separateBytes(byte[] in, int len) {
 int numOfBytes = (8 * in.length - 1) / len + 1;
 byte[] out = new byte[numOfBytes];
 for (int i = 0; i < numOfBytes; i++) {
 for (int j = 0; j < len; j++) {
 int val = extractBit(in, len * i + j);
 setBit(out, 8 * i + j, val);
 }
 }
 return out;
 }

 //Metodo utilizzato nella generazione delle subKeys, per concatenere le due metà della chiave.
 private static byte[] concatBits(byte[] a, int aLen, byte[] b, int bLen) {
 int numOfBytes = (aLen + bLen - 1) / 8 + 1;
 byte[] out = new byte[numOfBytes];
 int j = 0;
 for (int i = 0; i < aLen; i++) {
 int val = extractBit(a, i);
 setBit(out, j, val);
 j++;
 }
 for (int i = 0; i < bLen; i++) {
 int val = extractBit(b, i);
 setBit(out, j, val);
 j++;
 }
 return out;
 }

 /*
 * Elimina il padding.
 * Se il testo in chiaro non è un multiplo esatto,
 * è necessario riempire il tutto prima della cifratura (pad)
 * con l'aggiunta di una stringa di padding.
 * Quando si decodifica, la funzione ricevente (quella che che decripta)
 * ha bisogno di eliminare il padding.
 */
 private static byte[] deletePadding(byte[] input) {
 int count = 0;

int i = input.length - 1;
 while (input[i] == 0) {
 count++;
 i--;
 }

byte[] tmp = new byte[input.length - count - 1];
 System.arraycopy(input, 0, tmp, 0, tmp.length);
 return tmp;
 }
 /*Genera le SubKeys di ogni round. Inizialmente, vengono selezionati 56 bit della chiave
 * dagli iniziali 64 bit mediante la funzione permutFunc (PC-1) -
 * i rimanenti 8 bit sono scartati o utilizzati come bit di controllo della parità.
 * I 56 vengono poi suddivisi in 2 metà di 28 bit; ogni metà è poi trattata separatamente.
 * Nei cicli successivi entrambe le metà vengono fatte slittare verso sinistra di 1 o 2 bit
 * (per i round 1, 2, 9, 16 lo shift, cioè lo slittamento, è di 1 bit, per gli altri è di 2)
 * e quindi vengono scelti 48 bit per la sottochiave mediante la funzione Permuted Choice 2 (PC-2)
 * - 24 bit dalla metà di sinistra e 24 bit da quella di destra. La rotazione significa che
 * in ogni sottochiave è usato un insieme differente di bit; ogni bit è usato più o meno in
 * 14 delle 16 sottochiavi. Il gestore delle chiavi per la decifratura è simile -
 * deve generare le chiavi nell'ordine inverso quindi la rotazione è verso destra invece che verso
 * sinistra.
 */
 private static byte[][] generateSubKeys(byte[] key) {
 byte[][] tmp = new byte[16][];
 byte[] tmpK = permutFunc(key, PC1);

byte[] C = extractBits(tmpK, 0, PC1.length/2);
 byte[] D = extractBits(tmpK, PC1.length/2, PC1.length/2);

for (int i = 0; i < 16; i++) {

C = rotLeft(C, 28, keyShift[i]);
 D = rotLeft(D, 28, keyShift[i]);

byte[] cd = concatBits(C, 28, D, 28);

tmp[i] = permutFunc(cd, PC2);
 }

return tmp;
 }

 //è la funzione richiamata nel main che cripta il messaggio
 public static byte[] encrypt(byte[] data, byte[] key) {
 int lenght=0;
 byte[] padding = new byte[1];
 int i;
 lenght = 8 - data.length % 8;
 padding = new byte[lenght];
 padding[0] = (byte) 0x80;

 for (i = 1; i < lenght; i++)
 padding[i] = 0;

byte[] tmp = new byte[data.length + lenght];
 byte[] bloc = new byte[8];

K = generateSubKeys(key);

 int count = 0;

for (i = 0; i < data.length + lenght; i++) {
 if (i > 0 && i % 8 == 0) {
 bloc = encrypt64Bloc(bloc,K, false);
 System.arraycopy(bloc, 0, tmp, i - 8, bloc.length);
 }
 if (i < data.length)
 bloc[i % 8] = data[i];
 else{
 bloc[i % 8] = padding[count % 8];
 count++;
 }
 }
 if(bloc.length == 8){
 bloc = encrypt64Bloc(bloc,K, false);
 System.arraycopy(bloc, 0, tmp, i - 8, bloc.length);
 }
 return tmp;
 }





 //è la funzione richiamata nel main che decripta il messaggio
 public static byte[] decrypt(byte[] data, byte[] key) {
 int i;
 byte[] tmp = new byte[data.length];
 byte[] bloc = new byte[8];

 K = generateSubKeys(key);

for (i = 0; i < data.length; i++) {
 if (i > 0 && i % 8 == 0) {
 bloc = encrypt64Bloc(bloc,K, true);
 System.arraycopy(bloc, 0, tmp, i - 8, bloc.length);
 }
 if (i < data.length)
 bloc[i % 8] = data[i];
 }
 bloc = encrypt64Bloc(bloc,K, true);
 System.arraycopy(bloc, 0, tmp, i - 8, bloc.length);
 tmp = deletePadding(tmp);

return tmp;
 }
}
<pre>

An implementation of the algorithm AES 128-bit written in Java.

This standard specifies the Rijndael algorithm, a symmetric block cipher that can process data blocks of 128 bits, using cipher keys with lengths of 128, 192, and 256 bits. Rijndael was designed to handle additional block sizes and key lengths, however they are not adopted in this standard.

Throughout the remainder of this standard, the algorithm specified herein will be referred to as “the AES algorithm.” The algorithm may be used with the three different key lengths indicated above, and therefore these different “flavors” may be referred to as “AES-128”, “AES-192”, and “AES-256”. The version implemented below is 128-bit (AES-128). Code comments are written in Italian.

High-level description of the algorithm

  1. KeyExpansion—round keys are derived from the cipher key using Rijndael’s key schedule
  2. Initial Round
    1. AddRoundKey—each byte of the state is combined with the round key using bitwise xor
  3. Rounds
    1. SubBytes—a non-linear substitution step where each byte is replaced with another according to a lookup table.
    2. ShiftRows—a transposition step where each row of the state is shifted cyclically a certain number of steps.
    3. MixColumns—a mixing operation which operates on the columns of the state, combining the four bytes in each column.
    4. AddRoundKey
  4. Final Round (no MixColumns)
    1. SubBytes
    2. ShiftRows
    3. AddRoundKey
For more information about AES Encryption, see here.

This is the main class written in java:


import java.io.UTFDataFormatException;
import java.nio.charset.Charset;
/**
 *
 * @author Paolo Musolino
 */
public class EsameCrittografia {

private static final Charset UTF8_CHARSET = Charset.forName("UTF-8");
 /**
 * @param args
 */
 public static void main(String[] args) {


 try{

String textClar = "Prova di criptaggio con AES";
 //AES
 String j = "1a25s8fe5dsg65ad";
 System.out.println("Text in chiaro: "+textClar);
 byte[] encr = AES.encrypt(textClar.getBytes(), j.getBytes());
 System.out.println("Testo criptato con AES: "+new String(encr));

byte[] decr = AES.decrypt(encr, j.getBytes());
 System.out.println("Testo decriptato con AES: "+new String(decr));
 System.out.println("------------------");



 }catch(Exception e){
 e.printStackTrace();
 }
 }

}

This is the implementation class of AES-128bit.


/*
 * @author pmusolino
 */
public class AES {

/*
 * Nb: numero di colonne degli states (matrici). In questo caso 4. (Matrici 4x4)
 * Nk: numero di word della chiave, 4 in questo caso.
 * Nr: numero di round, 10 in questo caso
 */
 private static int Nb, Nk, Nr;
 private static byte[][] w; //memorizza le subKeys

/*
 * La S-box utilizzata è derivata da una funzione inversa nel campo finito GF(2^8),
 * conosciuta per avere delle ottime proprietà di non linearità.
 * Per evitare un potenziale attacco basato sulle proprietà algebriche la S-box
 * è costruita combinando la funzione inversa con una trasformazione affine invertibile.
 * La S-box è stata scelta con cura per non possedere né punti fissi né punti fissi opposti.
 * La S-box utilizzata in questo algoritmo è liberamente disponibile sul web.
 */
 private static int[] sbox = { 0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F,
 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76, 0xCA, 0x82,
 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C,
 0xA4, 0x72, 0xC0, 0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC,
 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15, 0x04, 0xC7, 0x23,
 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27,
 0xB2, 0x75, 0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52,
 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84, 0x53, 0xD1, 0x00, 0xED,
 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58,
 0xCF, 0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9,
 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8, 0x51, 0xA3, 0x40, 0x8F, 0x92,
 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
 0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E,
 0x3D, 0x64, 0x5D, 0x19, 0x73, 0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A,
 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB, 0xE0,
 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62,
 0x91, 0x95, 0xE4, 0x79, 0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E,
 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08, 0xBA, 0x78,
 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B,
 0xBD, 0x8B, 0x8A, 0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E,
 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E, 0xE1, 0xF8, 0x98,
 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55,
 0x28, 0xDF, 0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41,
 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16 };

/*
 *
 * S-box per il decrypt
 */
 private static int[] inv_sbox = { 0x52, 0x09, 0x6A, 0xD5, 0x30, 0x36, 0xA5,
 0x38, 0xBF, 0x40, 0xA3, 0x9E, 0x81, 0xF3, 0xD7, 0xFB, 0x7C, 0xE3,
 0x39, 0x82, 0x9B, 0x2F, 0xFF, 0x87, 0x34, 0x8E, 0x43, 0x44, 0xC4,
 0xDE, 0xE9, 0xCB, 0x54, 0x7B, 0x94, 0x32, 0xA6, 0xC2, 0x23, 0x3D,
 0xEE, 0x4C, 0x95, 0x0B, 0x42, 0xFA, 0xC3, 0x4E, 0x08, 0x2E, 0xA1,
 0x66, 0x28, 0xD9, 0x24, 0xB2, 0x76, 0x5B, 0xA2, 0x49, 0x6D, 0x8B,
 0xD1, 0x25, 0x72, 0xF8, 0xF6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xD4,
 0xA4, 0x5C, 0xCC, 0x5D, 0x65, 0xB6, 0x92, 0x6C, 0x70, 0x48, 0x50,
 0xFD, 0xED, 0xB9, 0xDA, 0x5E, 0x15, 0x46, 0x57, 0xA7, 0x8D, 0x9D,
 0x84, 0x90, 0xD8, 0xAB, 0x00, 0x8C, 0xBC, 0xD3, 0x0A, 0xF7, 0xE4,
 0x58, 0x05, 0xB8, 0xB3, 0x45, 0x06, 0xD0, 0x2C, 0x1E, 0x8F, 0xCA,
 0x3F, 0x0F, 0x02, 0xC1, 0xAF, 0xBD, 0x03, 0x01, 0x13, 0x8A, 0x6B,
 0x3A, 0x91, 0x11, 0x41, 0x4F, 0x67, 0xDC, 0xEA, 0x97, 0xF2, 0xCF,
 0xCE, 0xF0, 0xB4, 0xE6, 0x73, 0x96, 0xAC, 0x74, 0x22, 0xE7, 0xAD,
 0x35, 0x85, 0xE2, 0xF9, 0x37, 0xE8, 0x1C, 0x75, 0xDF, 0x6E, 0x47,
 0xF1, 0x1A, 0x71, 0x1D, 0x29, 0xC5, 0x89, 0x6F, 0xB7, 0x62, 0x0E,
 0xAA, 0x18, 0xBE, 0x1B, 0xFC, 0x56, 0x3E, 0x4B, 0xC6, 0xD2, 0x79,
 0x20, 0x9A, 0xDB, 0xC0, 0xFE, 0x78, 0xCD, 0x5A, 0xF4, 0x1F, 0xDD,
 0xA8, 0x33, 0x88, 0x07, 0xC7, 0x31, 0xB1, 0x12, 0x10, 0x59, 0x27,
 0x80, 0xEC, 0x5F, 0x60, 0x51, 0x7F, 0xA9, 0x19, 0xB5, 0x4A, 0x0D,
 0x2D, 0xE5, 0x7A, 0x9F, 0x93, 0xC9, 0x9C, 0xEF, 0xA0, 0xE0, 0x3B,
 0x4D, 0xAE, 0x2A, 0xF5, 0xB0, 0xC8, 0xEB, 0xBB, 0x3C, 0x83, 0x53,
 0x99, 0x61, 0x17, 0x2B, 0x04, 0x7E, 0xBA, 0x77, 0xD6, 0x26, 0xE1,
 0x69, 0x14, 0x63, 0x55, 0x21, 0x0C, 0x7D };

/*
 * Questa S-box viene utilizzata per generare le sub-keys dei vari passaggi dell'aes
 */
 private static int Rcon[] = { 0x8d, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36, 0x6c, 0xd8, 0xab, 0x4d, 0x9a,
 0x2f, 0x5e, 0xbc, 0x63, 0xc6, 0x97, 0x35, 0x6a, 0xd4, 0xb3, 0x7d, 0xfa, 0xef, 0xc5, 0x91, 0x39,
 0x72, 0xe4, 0xd3, 0xbd, 0x61, 0xc2, 0x9f, 0x25, 0x4a, 0x94, 0x33, 0x66, 0xcc, 0x83, 0x1d, 0x3a,
 0x74, 0xe8, 0xcb, 0x8d, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36, 0x6c, 0xd8,
 0xab, 0x4d, 0x9a, 0x2f, 0x5e, 0xbc, 0x63, 0xc6, 0x97, 0x35, 0x6a, 0xd4, 0xb3, 0x7d, 0xfa, 0xef,
 0xc5, 0x91, 0x39, 0x72, 0xe4, 0xd3, 0xbd, 0x61, 0xc2, 0x9f, 0x25, 0x4a, 0x94, 0x33, 0x66, 0xcc,
 0x83, 0x1d, 0x3a, 0x74, 0xe8, 0xcb, 0x8d, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b,
 0x36, 0x6c, 0xd8, 0xab, 0x4d, 0x9a, 0x2f, 0x5e, 0xbc, 0x63, 0xc6, 0x97, 0x35, 0x6a, 0xd4, 0xb3,
 0x7d, 0xfa, 0xef, 0xc5, 0x91, 0x39, 0x72, 0xe4, 0xd3, 0xbd, 0x61, 0xc2, 0x9f, 0x25, 0x4a, 0x94,
 0x33, 0x66, 0xcc, 0x83, 0x1d, 0x3a, 0x74, 0xe8, 0xcb, 0x8d, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20,
 0x40, 0x80, 0x1b, 0x36, 0x6c, 0xd8, 0xab, 0x4d, 0x9a, 0x2f, 0x5e, 0xbc, 0x63, 0xc6, 0x97, 0x35,
 0x6a, 0xd4, 0xb3, 0x7d, 0xfa, 0xef, 0xc5, 0x91, 0x39, 0x72, 0xe4, 0xd3, 0xbd, 0x61, 0xc2, 0x9f,
 0x25, 0x4a, 0x94, 0x33, 0x66, 0xcc, 0x83, 0x1d, 0x3a, 0x74, 0xe8, 0xcb, 0x8d, 0x01, 0x02, 0x04,
 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36, 0x6c, 0xd8, 0xab, 0x4d, 0x9a, 0x2f, 0x5e, 0xbc, 0x63,
 0xc6, 0x97, 0x35, 0x6a, 0xd4, 0xb3, 0x7d, 0xfa, 0xef, 0xc5, 0x91, 0x39, 0x72, 0xe4, 0xd3, 0xbd,
 0x61, 0xc2, 0x9f, 0x25, 0x4a, 0x94, 0x33, 0x66, 0xcc, 0x83, 0x1d, 0x3a, 0x74, 0xe8, 0xcb };

// Metodo che calcola lo xor tra array di byte, utilizzata nel metodo per generare le subKeys
 private static byte[] xor_func(byte[] a, byte[] b) {
 byte[] out = new byte[a.length];
 for (int i = 0; i < a.length; i++) {
 out[i] = (byte) (a[i] ^ b[i]);
 }
 return out;

}
 // Genero le varie subkeys di ogni round.
 private static byte[][] generateSubkeys(byte[] key) {
 byte[][] tmp = new byte[Nb * (Nr + 1)][4];

int i = 0;
 while (i < Nk) {

tmp[i][0] = key[i * 4];
 tmp[i][1] = key[i * 4 + 1];
 tmp[i][2] = key[i * 4 + 2];
 tmp[i][3] = key[i * 4 + 3];
 i++;
 }
 i = Nk;
 while (i < Nb * (Nr + 1)) {
 byte[] temp = new byte[4];
 for(int k = 0;k<4;k++)
 temp[k] = tmp[i-1][k];
 if (i % Nk == 0) {
 temp = SubWord(rotateWord(temp)); //effettua lo xor con Rcon
 temp[0] = (byte) (temp[0] ^ (Rcon[i / Nk] & 0xff));
 } else if (Nk > 6 && i % Nk == 4) {
 temp = SubWord(temp);
 }
 tmp[i] = xor_func(tmp[i - Nk], temp);
 i++;
 }

return tmp;
 }

/*
 * effettua una sostituzione di byte per ogni byte della parola in ingresso utilizzando la S-box
 */
 private static byte[] SubWord(byte[] in) {
 byte[] tmp = new byte[in.length];

for (int i = 0; i < tmp.length; i++)
 tmp[i] = (byte) (sbox[in[i] & 0x000000ff] & 0xff);

return tmp;
 }

/* esegue uno shift circolare di byte a sinistra su una parola. Per esempio:
 * rotateWord[b0,b1,b2,b3] = [b1,b2,b3,b0]
 */
 private static byte[] rotateWord(byte[] input) {
 byte[] tmp = new byte[input.length];
 tmp[0] = input[1];
 tmp[1] = input[2];
 tmp[2] = input[3];
 tmp[3] = input[0];

return tmp;
 }

/*
 * Il passaggio AddRoundKey combina con uno XOR la chiave di sessione con la matrice ottenuta
 * dai passaggi precedenti (State). Una chiave di sessione viene ricavata dalla chiave primaria
 * ad ogni round, attraverso il gestore delle chiavi.
 * Un AddRoundKey viene eseguito all'inizio di tutto.
 */
 private static byte[][] AddRoundKey(byte[][] state, byte[][] w, int round) {

byte[][] tmp = new byte[state.length][state[0].length];

for (int c = 0; c < Nb; c++) {
 for (int l = 0; l < 4; l++)
 tmp[l] = (byte) (state[l] ^ w[round * Nb + c][l]);
 }

return tmp;
 }

/*
 * Nel passaggio SubBytes ogni byte della matrice viene modificato tramite la S-box a 8 bit.
 * Questa operazione provvede a fornire la non linearità all'algoritmo.
 * La S-box utilizzata è derivata da una funzione inversa nel campo finito GF(2^8),
 * conosciuta per avere delle ottime proprietà di non linearità.
 *
 */
 private static byte[][] SubBytes(byte[][] state) {

byte[][] tmp = new byte[state.length][state[0].length];
 for (int row = 0; row < 4; row++)
 for (int col = 0; col < Nb; col++)
 tmp[row][col] = (byte) (sbox[(state[row][col] & 0x000000ff)] & 0xff);

return tmp;
 }

 /*
 * Nel passaggio SubBytes ogni byte della matrice viene modificato tramite la S-box a 8 bit.
 * Effettua il passaggio contrario a SubBytes, ricavando gli states dalla matrice inversa.
 */
 private static byte[][] InvSubBytes(byte[][] state) {
 for (int row = 0; row < 4; row++)
 for (int col = 0; col < Nb; col++)
 state[row][col] = (byte)(inv_sbox[(state[row][col] & 0x000000ff)]&0xff);

 return state;
 }

/* Il passaggio ShiftRows provvede a scostare le righe della matrice
 * di un parametro dipendente dal numero di riga. Nell'AES la prima riga
 * resta invariata, la seconda viene spostata di un posto verso sinistra,
 * la terza di due posti e la quarta di tre. In questo modo l'ultima colonna dei
 * dati in ingresso andrà a formare la diagonale della matrice in uscita.
 * Tutte le operazioni sono effettuate utilizzando l'indice della colonna “modulo”
 * il numero di colonne.
 */
 private static byte[][] ShiftRows(byte[][] state) {

byte[] t = new byte[4];
 for (int r = 1; r < 4; r++) {
 for (int c = 0; c < Nb; c++)
 t = state[r][(c + r) % Nb];
 for (int c = 0; c < Nb; c++)
 state[r] = t;
 }

return state;
 }

 /*
 * Il passaggio contrario a ShiftRows per il decrypt.
 */
 private static byte[][] InvShiftRows(byte[][] state) {
 byte[] t = new byte[4];
 for (int r = 1; r < 4; r++) {
 for (int c = 0; c < Nb; c++)
 t[(c + r)%Nb] = state[r];
 for (int c = 0; c < Nb; c++)
 state[r] = t;
 }
 return state;
 }

//Il contrario di MixColumns, serve per decriptare.
 private static byte[][] InvMixColumns(byte[][] s){
 int[] sp = new int[4];
 byte b02 = (byte)0x0e, b03 = (byte)0x0b, b04 = (byte)0x0d, b05 = (byte)0x09;
 for (int c = 0; c < 4; c++) {
 sp[0] = FFMul(b02, s[0]) ^ FFMul(b03, s[1]) ^ FFMul(b04,s[2]) ^ FFMul(b05,s[3]);
 sp[1] = FFMul(b05, s[0]) ^ FFMul(b02, s[1]) ^ FFMul(b03,s[2]) ^ FFMul(b04,s[3]);
 sp[2] = FFMul(b04, s[0]) ^ FFMul(b05, s[1]) ^ FFMul(b02,s[2]) ^ FFMul(b03,s[3]);
 sp[3] = FFMul(b03, s[0]) ^ FFMul(b04, s[1]) ^ FFMul(b05,s[2]) ^ FFMul(b02,s[3]);
 for (int i = 0; i < 4; i++) s[i] = (byte)(sp[i]);
 }

 return s;
 }

 /*
 * Il passaggio MixColumns prende i quattro byte di ogni colonna e li combina
 * utilizzando una trasformazione lineare invertibile
 * Nel passaggio MixColumns ogni colonna di byte viene moltiplicata
 * per un polinomio fisso c(x).
 */
 private static byte[][] MixColumns(byte[][] s){
 int[] sp = new int[4];
 byte b02 = (byte)0x02, b03 = (byte)0x03;
 for (int c = 0; c < 4; c++) {
 sp[0] = FFMul(b02, s[0]) ^ FFMul(b03, s[1]) ^ s[2] ^ s[3];
 sp[1] = s[0] ^ FFMul(b02, s[1]) ^ FFMul(b03, s[2]) ^ s[3];
 sp[2] = s[0] ^ s[1] ^ FFMul(b02, s[2]) ^ FFMul(b03, s[3]);
 sp[3] = FFMul(b03, s[0]) ^ s[1] ^ s[2] ^ FFMul(b02, s[3]);
 for (int i = 0; i < 4; i++) s[i] = (byte)(sp[i]);
 }

 return s;
 }
 //Con questa funzione i byte "a" e "b" si moltiplicano lentamente utilizzando gli shift
 //Utilizzata in MixColumns
 public static byte FFMul(byte a, byte b) {
 byte aa = a, bb = b, r = 0, t;
 while (aa != 0) {
 if ((aa & 1) != 0)
 r = (byte) (r ^ bb);
 t = (byte) (bb & 0x80);
 bb = (byte) (bb << 1);
 if (t != 0)
 bb = (byte) (bb ^ 0x1b);
 aa = (byte) ((aa & 0xff) >> 1);
 }
 return r;
 }

//Per cifrare ogni blocco di 128 bit viene utilizzata questa funzione.
 public static byte[] encryptBloc(byte[] in) {
 byte[] tmp = new byte[in.length];

byte[][] state = new byte[4][Nb];

for (int i = 0; i < in.length; i++)
 state[i / 4][i % 4] = in[i%4*4+i/4];

state = AddRoundKey(state, w, 0);
 for (int round = 1; round < Nr; round++) {
 state = SubBytes(state);
 state = ShiftRows(state);
 state = MixColumns(state);
 state = AddRoundKey(state, w, round);
 }
 state = SubBytes(state);
 state = ShiftRows(state);
 state = AddRoundKey(state, w, Nr);

for (int i = 0; i < tmp.length; i++)
 tmp[i%4*4+i/4] = state[i / 4][i%4];

return tmp;
 }

//Per decrifrare ogni blocco di 128 bit viene utilizzata questa funzione
 public static byte[] decryptBloc(byte[] in) {
 byte[] tmp = new byte[in.length];

byte[][] state = new byte[4][Nb];

for (int i = 0; i < in.length; i++)
 state[i / 4][i % 4] = in[i%4*4+i/4];

state = AddRoundKey(state, w, Nr);
 for (int round = Nr-1; round >=1; round--) {
 state = InvSubBytes(state);
 state = InvShiftRows(state);
 state = AddRoundKey(state, w, round);
 state = InvMixColumns(state);

 }
 state = InvSubBytes(state);
 state = InvShiftRows(state);
 state = AddRoundKey(state, w, 0);

for (int i = 0; i < tmp.length; i++)
 tmp[i%4*4+i/4] = state[i / 4][i%4];

return tmp;
 }

 /*Questa funzione che viene richiamata all'interno del main, provvede a criptare la stringa
 * di byte in ingresso, richiamando encryptBloc
 */
 public static byte[] encrypt(byte[] in,byte[] key){

 Nb = 4;
 Nk = key.length/4;
 Nr = Nk + 6;


 int lenght=0;
 byte[] padding = new byte[1];
 int i;
 lenght = 16 - in.length % 16;
 padding = new byte[lenght];
 padding[0] = (byte) 0x80;

 for (i = 1; i < lenght; i++)
 padding[i] = 0;

byte[] tmp = new byte[in.length + lenght];
 byte[] bloc = new byte[16];


 w = generateSubkeys(key);

 int count = 0;

for (i = 0; i < in.length + lenght; i++) {
 if (i > 0 && i % 16 == 0) {
 bloc = encryptBloc(bloc);
 System.arraycopy(bloc, 0, tmp, i - 16, bloc.length);
 }
 if (i < in.length)
 bloc[i % 16] = in[i];
 else{
 bloc[i % 16] = padding[count % 16];
 count++;
 }
 }
 if(bloc.length == 16){
 bloc = encryptBloc(bloc);
 System.arraycopy(bloc, 0, tmp, i - 16, bloc.length);
 }

 return tmp;
 }

 /*Questa funzione che viene richiamata all'interno del main, provvede a decriptare la stringa
 * di byte in ingresso, richiamando dencryptBloc
 */
 public static byte[] decrypt(byte[] in,byte[] key){
 int i;
 byte[] tmp = new byte[in.length];
 byte[] bloc = new byte[16];


 Nb = 4;
 Nk = key.length/4;
 Nr = Nk + 6;
 w = generateSubkeys(key);
 for (i = 0; i < in.length; i++) {
 if (i > 0 && i % 16 == 0) {
 bloc = decryptBloc(bloc);
 System.arraycopy(bloc, 0, tmp, i - 16, bloc.length);
 }
 if (i < in.length)
 bloc[i % 16] = in[i];
 }
 bloc = decryptBloc(bloc);
 System.arraycopy(bloc, 0, tmp, i - 16, bloc.length);
 tmp = deletePadding(tmp);

return tmp;
 }

 /*
 * Elimina il padding inserito nell'elaborazione della stringa iniziale,
 * e viene utilizzato solo nel momento del decrypt del testo cifrato, per tornare al testo
 * iniziale.
 */
 private static byte[] deletePadding(byte[] input) {
 int count = 0;

int i = input.length - 1;
 while (input[i] == 0) {
 count++;
 i--;
 }

byte[] tmp = new byte[input.length - count - 1];
 System.arraycopy(input, 0, tmp, 0, tmp.length);
 return tmp;
 }

}

Fibonacci Search Algorithm, written in C

The Fibonacci search technique is a method of searching a sorted array using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers. Compared to binary search, Fibonacci search examines locations whose addresses have lower dispersion. Therefore, when the elements being searched have non-uniform access memory storage (i.e., the time needed to access a storage location varies depending on the location previously accessed), the Fibonacci search has an advantage over binary search in slightly reducing the average time needed to access a storage location. The typical example of non-uniform access storage is that of a magnetic tape, where the time to access a particular element is proportional to its distance from the element currently under the tape’s head. Note, however, that large arrays not fitting in cache or even in RAM can also be considered as non-uniform access examples. Fibonacci search has a complexity of O(log(x)).

Fibonacci Search Algorithm, written in C:

#include <stdio.h>

int ricerca_fib(int a[], int n, long x)
{ 
	int inf=0, pos, k;
	static int kk= -1, nn=-1, fib[]={0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141};

if(nn!=n)
{ 
	k=0;
	while(fib[k]<n) k++;
	kk=k;
	nn=n;
}
else
	k=kk;

while(k>0)
{
	pos=inf+fib[--k];
	if((pos>=n)||(x<a[pos]));
	else if (x>a[pos])
	{
		inf=pos+1;
		k--;
    }

	else {
		return pos;
	}
}
	return -1;
}

Recursive Quicksort Algorithm written in C language [with example step-by-step]

Quicksort is a sorting algorithm developed by C. A. R. Hoare that, on average, makes O(nlogn) (big O notation) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though if implemented correctly this behavior is rare. Typically, quicksort is significantly faster in practice than other O(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data, it is possible to make design choices that minimize the probability of requiring quadratic time. Additionally, quicksort tends to make excellent usage of the memory hierarchy, taking perfect advantage of virtual memory and available caches. Although quicksort is usually not implemented as an in-place sort, it is possible to create such an implementation.
Quicksort (also known as “partition-exchange sort”) is a comparison sort and, in efficient implementations, is not a stable sort.
Continue reading Recursive Quicksort Algorithm written in C language [with example step-by-step]

Massimo e Minimo di un array in C

Con le seguenti funzioni, scritte in linguaggio C, è possibile trovare il valore massimo e il valore minimo all’interno di un array di n elementi interi. Con piccolissime modifiche è possibile scrivere la versione che valuta il massimo e il minimo di un array su valori in virgola mobile (float).

Continue reading Massimo e Minimo di un array in C

Binary Search Algorithm, written in C [with video example step-to-step]

In computer science, a binary search is an algorithm for locating the position of an item in a sorted array.[1][2] Binary search works by comparing an input value to the middle element of the array. The comparison determines whether the element is equal to the input, less than the input or greater. When the element being compared to equals the input the search stops and typically returns the position of the element. If the element is not equal to the input then a comparison is made to determine whether the input is less than or greater than the element. Depending on which it is the algorithm then starts over but only searching the top or bottom subset of the array’s elements. If the input is not located within the array the algorithm will usually output a unique value indicating this. This method halves the number of items to check each time, so it finds it or determines it’s not present in logarithmic time. A binary search is a dichotomic divide and conquer search algorithm.
It is useful to find where an item is in a sorted array. For example, if you had an array for contact information, with people’s names, addresses, and telephone numbers sorted by name, you could use binary search to find out a few useful facts: whether the person’s information is in the array, what the person’s address is, and what the person’s telephone number is.
Continue reading Binary Search Algorithm, written in C [with video example step-to-step]

Linear Search in unordered array [with source code written in C and video example]

In computer science, linear search or sequential search is a method for finding a particular value in a list, that consists of checking every one of its elements, one at a time and in sequence, until the desired one is found.[1]
Linear search is the simplest search algorithm; it is a special case of brute-force search. Its worst case cost is proportional to the number of elements in the list; and so is its expected cost, if all list elements are equally likely to be searched for. Therefore, if the list has more than a few elements, other methods (such as binary search or hashing) may be much more efficient. Linear search is usually very simple to implement, and is practical when the list has only a few elements, or when performing a single search in an unordered list. When many values have to be searched in the same list, it often pays to pre-process the latter in order to use a faster method. For example, one may sort the list and use binary search, or build any efficient search data structure from it.

This is an implementation of Linear Search in C Language, with Main structure.

Source Code


// © Codeido - www.codeido.com - Developed by Paolo Musolino

//Ricerca sequenziale in un array disordinato
#include <stdio.h>

int ricerca_Sequenziale(int a[], int n, int chiave)
{
	int i=0;
	
	while ((a[i]) && (i<n))
		   {
			   if (a[i]==chiave) 
			   {
				   return i;
				   
			   }
			   
			   if (i==n-1) 
			   {
				   return -1;
			   }
			   
			   if(a[i]!=chiave)
				   i++;
			   
		   }
	
}



int main ()
{
	int a[14]={5, 10, 11, 9, 7, 8, 4, 5, 7, 2, 45, 1, 4, 20};
	int ris_ricerca;
	ris_ricerca = ricerca_Sequenziale(a, 14, 20);
	printf("\n");
	
	if (ris_ricerca==-1) {
		printf("L'elemento cercato non è presente all'interno dell'array\n");
	}
	
	if (ris_ricerca>=0) {
		printf("L'elemento cercato si trova nella posizione %d ", ris_ricerca);
	}
	
	return 0;
}

Non-uniform probabilities
The performance of linear search improves if the desired value is more likely to be near the beginning of the list than to its end. Therefore, if some values are much more likely to be searched than others, it is desirable to place them at the beginning of the list.
In particular, when the list items are arranged in order of decreasing probability, and these probabilities are geometrically distributed, the cost of linear search is only O(1). If the table size n is large enough, linear search will be faster than binary search, whose cost is O(log n).[1]

Linear and Binary Searching

Studio dell’indice di condizionamento su alcune classi di matrici, rispetto alla norma 1 [FORTRAN 77]

Il condizionamento in matematica, in particolare nel calcolo numerico, riguarda il rapporto tra errore commesso sul risultato di un calcolo e incertezza sui dati in ingresso. Un problema è ben condizionato quando la soluzione del problema con delle piccole variazioni, non differisce molto dalla soluzione del problema originale; al contrario, un problema mal condizionato è un problema dove le soluzioni sono molto sensibili a piccole perturbazioni dei dati iniziali. In questo programma, scritto in FORTRAN 77, viene studiato l’indice di condizionamento delle matrici di Toepliz, Henkel, Vandermonde e Wilkinson rispetto alla norma 1.

Source Code:

cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
c 			  Realizzazione a cura di: 												   
c 			- Paolo Musolino			
c 			- Maria Emanuela Aricò
c 			- Armando Ruggeri
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc

	PROGRAM main

	PARAMETER (n=4)
	REAL h(n,n), t(n,n), k(n,n), v(n,n), w(n,n), z(n,n), cond
	cond=0

c PREMESSA
	WRITE (*,*) '****************************************************'
	WRITE (*,*) 'Studio indice di condizionamento delle matrici'
	WRITE (*,*) 'di Toepliz, Henkel, Vandermonde e Wilkinson per la'
	WRITE (*,*) 'norma 1'
	WRITE (*,*) '****************************************************'
	WRITE (*,*)

c CREAZIONE MATRICI
	CALL hilbert(h, n)
	CALL toepliz(t, n)
	CALL toepliz2(z,n)
	CALL henkel(k, n)
	CALL vandermonde(v, n)
	CALL wilkinson (w, n)

c CALCOLO  E STAMPA CONDIZIONAMENTO
 	WRITE (*,*)
	WRITE (*,*) 'Indici di condizionamento' 
	CALL condz(h, n, cond)
	WRITE (*,*) 'Hilbert      :     ', cond
	CALL condz(t, n, cond)
	WRITE (*,*) 'Toepliz d.d  :     ', cond
	CALL condz(z, n, cond)
	WRITE (*,*) 'Toepliz n.d.d:     ', cond	
	CALL condz(k, n, cond)
	WRITE (*,*) 'Henkel       :     ', cond
	CALL condz(v, n, cond)
	WRITE (*,*) 'Vandermonde  :     ', cond
	CALL condz(w, n, cond)
	WRITE (*,*) 'Wilkinson    :     ', cond

	END

c SUBROUTINE DEL CALCOLO DELLE NORME
	SUBROUTINE norma (a, n, n1)

	INTEGER n
	REAL a(n,n), n1, x
	n1=0
	x=0

	DO j=1, n
	  DO i=1, n
	    x = x + abs(a(i,j))
	  ENDDO
	  IF(x .gt. n1) THEN
	      n1 = x
	  ENDIF
	  x = 0
	ENDDO

	END

		SUBROUTINE condz (a, n, cond)

	USE MSIMSL

	REAL a(n,n), ainv(n,n), cond, n1, n1inv
	PARAMETER  (lda=4, ldainv=4)
	CALL azzera(cond)
	n1 = 0
c CALCOLO INVERSA
	CALL LINRG (n, a, lda, ainv, ldainv)

c CALCOLO NORMA MATRICE
	CALL norma(a, n, n1)
c	WRITE (*,*) 'Norma 1        : ', n1
c CALCOLO NORMA MATRICE INVERSA
	CALL norma(ainv, n, n1inv)
c	WRITE (*,*) 'Norma 1 inversa: ', n1inv

c CALCOLO CONDIZIONAMENTO
	cond = n1 * n1inv

	END

	SUBROUTINE azzera (x)
	REAL x
	x=0
	END  

c MATRICE HILBERT
	SUBROUTINE hilbert (h, n)
	INTEGER n,i,j
	REAL h(n,n)
	DO i=1, n
	  DO j=1, n
	    h(i,j) = 1./(i+j-1)
	  ENDDO
	ENDDO
      WRITE (*,*) 'Matrice di Hilbert:' 
      DO i=1, n
	  WRITE (*,*) (h(i,j), j=1, n)
	ENDDO
	END

c MATRICE TOEPLIZ	DIAG. DOMINANTE
	SUBROUTINE toepliz (t, n)
	integer n,i,j 
	real vet(-(n-1):(n-1)),t(n,n)
	do i=-(n-1), (n-1)
	   vet(i) = 1
      enddo 
	write(*,*) 'Inserire vettore di 3 elementi per Toepliz d.d.'
	read (*,*) (vet(i), i=-1, 1)
	do i=1,n
	  do j=1,n
	    t(i,j)=vet(j-i)
	  enddo
	enddo
	write(*,*)'La matrice di Toepliz:'
	DO i=1, n
	WRITE (*,*) (t(i,j), j=1, n)
	ENDDO	
	END

c MATRICE TOEPLIZ
	SUBROUTINE toepliz2 (t, n)
	integer n,i,j 
	real vet(-(n-1):(n-1)),t(n,n)
	do i=-(n-1), (n-1)
	   vet(i) = 1
      enddo 
	write(*,*) 'Inserire vettore di 3 elementi per Toepliz non d.d.'
	read (*,*) (vet(i), i=-1, 1)
	do i=1,n
	  do j=1,n
	    t(i,j)=vet(j-i)
	  enddo
	enddo
	write(*,*)'La matrice di Toepliz:'
	DO i=1, n
	WRITE (*,*) (t(i,j), j=1, n)
	ENDDO	
	END

c MATRICE HENKEL
	SUBROUTINE henkel (k, n)
	integer n,i,j
	real vet(-(n-1):(n-1)),k(n,n) 
	do i=-(n-1), (n-1)
	   vet(i) = 1
      enddo 
	write(*,*) 'Inserire vettore di 3 elementi per la matrice Henkel'
	read (*,*) (vet(i), i=-1, 1)
	do i=1,n
	  do j=1,n
	    k(i,j)=vet(i+j-(n+1))
	  enddo
	enddo
	write(*,*)'La matrice di Henkel:'
	DO i=1, n
	WRITE (*,*) (k(i,j), j=1, n)
	ENDDO	
	END

c MATRICE VANDERMONDE
	SUBROUTINE vandermonde (k, n)
	integer n,i,j
	real k(n,n),vet(n),a,b,x
	write(*,*) 'Inserire estremo a per la matrice Vandermonde'
	read (*,*) a
	write(*,*) 'Inserire estremo b per la matrice Vandermonde'
	read (*,*) b
	x = (b-a)/(n-1)
	do i=1, n
	  vet(i) = a + (i-1)*x
	enddo
	do i=1,n
	  do j=1,n
	    k(i,j)=vet(i)**(j-1)
	  enddo
	enddo
	write(*,*)'La matrice di Vandermonde:'
	DO i=1, n
	   WRITE (*,*) (k(i,j), j=1, n)
	ENDDO	
	END

c MATRICE WILKINSON
	SUBROUTINE wilkinson (w, n)
	integer n,i,j
	REAL w(n,n)
	DO i=1, n
	  DO j=1, n
	    IF (i .eq. j) THEN
	       w(i,j) = 1
		ELSE IF (i .gt. j) THEN
		   w(i,j) = (-1)**(j-i+1)
		ELSE IF ((i .lt. j) .and. (j .eq. n)) THEN
		   w(i,j) = (-1)**i
		ELSE
		   w(i,j) = 0
		ENDIF
	  ENDDO
	ENDDO
	WRITE (*,*) 'La matrice di Wilkinson:'
	DO i=1, n
	  WRITE (*,*) (w(i,j), j=1, n)
	ENDDO	
	END
 

Eseguendo il nostro programma, possiamo vedere che l’ indice di condizionamento, rispetto alla norma 1, è molto alto per la matrice di Hilbert. Sono stati restituiti degli alti valori anche per quelli della matrice di Henkel. E’ bene notare che se la Toepliz diagonale dominante e la Toepliz non diagonale dominante hanno gli stessi valori, la Toepliz non diagonale dominante presenta un indice di condizionamento peggiore di quella diagonale dominante. Possiamo affermare, infine, che la matrice di Toepliz diagonale dominante, insieme a quella di Wilkinson sono due esempi di matrici ben condizionate.

Leadsort written in C

The sorting algorithm “leadsort” is a variant of “bubblesort” that allows you to sort the array in reverse. Computational complexity= O(n^2).

Source Code written in C language:


// © Codeido - www.codeido.com - Developed by Paolo Musolino

#include <stdio.h>

void swap(int *a, int *b)
{	
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
	
	
}
//---------------//---------------//---------------
int confronto(int x, int y)
{
	if(x<y) return -1;
	else if(x>y) return 1;
	else {
		return 0;
	}
	
}

void leadSort(int a[], int n)
{
	int i, j;
	
	for (i=n; i>1; i--) {
		for (j=1; j<i; j++) {
			if (confronto(a[j],a[j-1])<0) {
				swap(&a[j], &a[j-1]);
			}
		}
	}
	
}

int main ()
{
	int a[14]={5, 10, 11, 9, 7, 8, 4, 5, 7, 2, 45, 1, 4, 20};
	int i;
	leadSort(a, 14);
	printf("\n");
	for (i=0; i<14; i++) {
		printf("%d ", a[i]);
	}
	
	
	return 0;
}

Bubblesort written in C with example step-by-step

Source code of sorting algorithm “bubblesort” written in C. Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements “bubble” to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort.

Step-by-step example
Let us take the array of numbers “5 1 4 2 8”, and sort the array from lowest number to greatest number using bubble sort algorithm. In each step, elements written in bold are being compared.

– First Pass:
( 5 1 4 2 8 ) ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps them.
( 1 5 4 2 8 ) ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
– Second Pass:
( 1 4 2 5 8 ) ( 1 4 2 5 8 )
( 1 4 2 5 8 ) ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
Third Pass:
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
Finally, the array is sorted, and the algorithm can terminate.

Source Code in C:


// © Codeido - www.codeido.com - Developed by Paolo Musolino

#include <stdio.h>

void swap(int *a, int *b)
{	
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
	
	
}
//---------------//---------------//---------------
int confronto(int x, int y)
{
	if(x<y) return -1;
	else if(x>y) return 1;
	else {
		return 0;
	}
	
}

void bubbleSort(int a[], int n)
{
	int i, j;
	for (i=0; i<n-1; i++) 
	{
		for (j=n-1; j>i; j--) 
		{
			if (confronto(a[j], a[j-1])<0) 
			
				swap(&a[j], &a[j-1]);
			
		}
	}
}


//Main Function
int main ()
{
	int a[14]={5, 10, 11, 9, 7, 8, 4, 5, 7, 2, 45, 1, 4, 20};
	int i;
	bubbleSort(a, 14);
	printf("\n");
	for (i=0; i<14; i++) {
		printf("%d ", a[i]);
	}
	
	
	return 0;
}

[retweet]