XOR und Geschwindigkeit

[Matze007]

Hallo,

ich möchte eine große Datei(>200MB) einlesen und dann eine"Prüfsumme" bilden:
Das soll so ablaufen, dass 16Byte Blöcke mit XOR verknüpft werden.
Also der erste 16Byte Block mit dem zweiten 16Byte Block und das Ergbnis wieder mit dem nächsten(dritten) 16 Byte Block usw.

Ich habe auch schon mal ein Programm geschrieben, ich bin aber noch nicht mit der Geschwindigkeit zufrieden. Über Ideen wie ich das schneller machbar ist würde ich mich sehr freuen!! Hier mein Programm:

import java.io.*;

public class Xor{
	public static void main(String[] args){
		long start = System.currentTimeMillis();
		int nbytes;
 		byte[] feld = new byte[16];
 		byte[] hilf = new byte[16];
 		byte[] hilf2 = new byte[16];
		int pos=0;
		
		try{
			File ein = new File(args[0]);
			long laenge = ein.length();
			int n16 = (int)(laenge/16);	//Anzahl volle 16Byte -Blöcke
			int rest = (int)(laenge-n16*16);
							
			FileInputStream fis = new FileInputStream(args[0]);
			BufferedInputStream bis = new BufferedInputStream(fis);
		
			while((nbytes=bis.read(hilf))!=-1){
				if(n16>0){				
					for(int i=0; i<nbytes; i++){
						pos = i%16;
						feld[pos]= (byte)(feld[pos]^hilf[i]);
						pos++;
					}
				}
				else {
					System.arraycopy(hilf,0,hilf2,0,rest);
					for(int i=0;i<rest;i++){
						feld[i]=(byte)(feld[i]^hilf2[i]);
						System.out.println("i  "+i);
					}
					break;
				}
				n16--;
			}
			fis.close();
			bis.close();
		}
			
		catch (Exception e) {}
		long end = System.currentTimeMillis();
		
		System.out.println("Zeit=  "+(end-start));
		StringBuffer sb = new StringBuffer("");
		for(int i=0; i<feld.length;i++){
			int q = feld[i];
			sb.append(Integer.toHexString(q)); 
		}
		System.out.println("Ergenis=  "+sb);

	}
}

Danke schon mal vorab!

 

[Ark]

Entferne erst einmal jedes System.out.println() bzw. print().

int rest = (int)(laenge-n16*16);
//ist äquivalent zu
int rest = (int)(laenge%16);
//ist äquivalent zu
int rest = (int)(laenge&15);


pos = i%16;
//ist äquivalent zu
pos = i&15;

Und noch eine Frage zu dem hier:

System.arraycopy(hilf,0,hilf2,0,rest);

Kann man das nicht anders lösen? Ich verstehe zwar gerade nicht den Code (insgesamt), aber ich vermute, dass sich das auch mit einem zweidimensionalen Array machen lässt. (Nur so eine Idee … ich verstehe den Code noch nicht ganz, wie gesagt.)

MfG
Ark

 

[Matze007]

Die unnötigen System.out.println's habe ich jetzt entfernt. Die Änderung zu laenge%15 und pos&15 habe ich auch erledigt.

Nochmal zu Erklärung was ich mit dem System.arraycopy(..) erreichen wollte:

Angenommen die Eingabedatei (b0,b1,...b33) besteht aus 34 Byte, dann sollte der 16Byte Ausagabeblock(a0,a1...a15) ungefähr so aussehen:

a0 = b0 XOR b16 XOR b32
a1 = b1 XOR b17 XOR b33
a2 = b2 XOR b18
a3 = b3 XOR b19
a4 = b4 XOR b20
a5 = b5 XOR b21
...
a15 = b15 XOR b31

mit dem System.arraycopy soll in diesem Fall die Besonderheit mit den zwei ersten Ausgabebyte behandelt werden.

Danke für die Hinweise soweit.
Die Eingabedatei ist wie gesagt sehr groß, um die Verarbeitung zu beschleunigen muss man sich glaube ich den Teil anschauen, in dem die Daten eingelesen und verarbeitet werden? Der Teil braucht bis jetzt am längsten.

 

[Roar]

benutz größere buffer zum lesen der daten, 4kb und mehr statt 16 byte

 

[Ark]

Soweit ich mich entsinnen kann, gelten für XOR doch das Assoziativ- und das Kommutativgesetz, oder?

(a ^ b) ^ c = a ^ (b ^ c)
a ^ b = b ^ a

Also ist das doch ganz einfach:

public class Xor{
    public static void main(String[] args) throws IOException{

    int nextByte;
    byte[] feld=new byte[16];
    int pos=0;// EDIT: Die Zeile habe ich
    //doch glatt vergessen, sorry.

    long start = System.currentTimeMillis();

    BufferedInputStream bis=new BufferedInputStream(
        new FileInputStream(args[0])
    );

    while((nextByte=bis.read())!=-1){//nur ein Byte einlesen,
        //das Puffern überlassen wir bis
        feld[pos&15]^=(byte)nextByte;//Kernoperation
        pos++;
    }
    bis.close();

    long end = System.currentTimeMillis();
    //Rest
}

feld muss natürlich zu Beginn mit 0 gefüllt sein, was ja auch schon so gegeben ist.

Das müsste die ganze Herrlichkeit gewesen sein. Oder irre ich?

Und: Es stimmt, benutze einfach den Puffer, so wie ihn der Standardkonstruktor des BufferedInputStream vorschlägt.

MfG
Ark

 

[Wildcard]

Bei großen Dateien kann sich auch FileChannel#map lohnen

 

[Matze007]

Ich habe das jetzt mal mit dem FileChannel ausprobiert und das geht wirklich um einiges schneller.
Vielen Dank für den Hinweis!!