Dateiverarbeitung in C

Neue Frage »

Auf diesen Beitrag antworten »
deppensido Dateiverarbeitung in C

hallo,

eigentlich soll es bei dieser Aufgabe um Threads und Speedup gehören, also das Programm mittels #pragma Anweisungen beschleunigen. Konkret soll hierzu eine Textdatei eingelesen und alle Wörter, die mindestens einmal vorkommen abgespeichert werden. Wir haben hierzu ein Codegerüst erhalten.
Hier ist auch schon mein erstes Problem: Ich verstehe nicht, wofür die Variablen "target" oder "hash" gut sind. Im Prinzip kann ich mit dem vorgegeben Code, bis auf das öffnen der Datei, nicht nachvollziehen.
Mit hilfe des buffer und der strtok() Funktion habe ich einen Versuch gemacht, die Wörter der Datei einzulesen. Hier mal der Code dazu:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
// You can use these includes and defines as a hint what functions you might want to use ;)
#define _GNU_SOURCE
#include "md5.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <omp.h>
#include <time.h>

#define HASH_LENGTH 16  //Wofür ist das?

int main (){
  
	//Bis zur Aufgabenstellung ist dieser Teil des Codes vorgegeben gewesen
	//die nächsten beiden Zeilen versteh ich nicht, wofür das gut ist
	// unsigned char target[HASH_LENGTH] = {0xe6, 0x54, 0x93, 0xcc, 0xde, 0xe9, 0xc4, 0x51, 0x4f, 0xe2, 0x0e, 0x04, 0x04, 0xf3, 0xbc, 0xb8}; "???" - to be used for les_miserables.txt
	unsigned char target[HASH_LENGTH] = {0x1c, 0x01, 0x43, 0xc6, 0xac, 0x75, 0x05, 0xc8, 0x86, 0x6d, 0x10, 0x27, 0x0a, 0x48, 0x0d, 0xec}; // "Les Miserables" - to be used for les_miserables_preface.txt
	time_t start = time(NULL);
	FILE* f;
	f = fopen("les_miserables_preface.txt", "r");
	
	if(f == NULL){
		return 1;
	}
	const char* delim = " .,;-:0123456789?!\"*+()|&[]#$/%%'"; 
	unsigned char hash[HASH_LENGTH] = {0};
	char buffer[1024];
	
	//Dies ist die Aufgabenstellung
	/*
	 * - find all unique words from the book
	 * - create the hashes of all two-string combinations
	 * - try to speed it up
	 * Usage example (not complete!):
	 */ 
	  //Dieser Teil des Codes ist von mir
	  char str[1024];
	  int i,j;
	  while(feof(f)==0) {
	    printf("%d",i);
	      for(i=0;i<1024;i++)
		buffer[i] = fgets(hash, HASH_LENGTH, f);//Buch einlesen
	  }
	  for(j=0;j<1024;j++) {
	    str[i] = strtok(buffer[i], delim);//Alle Wörter, die mindestens einmal vorkommen abspeichern
	    buffer[i] = str[i];
	  }
	//Der Rest des Codes war vorgegeben
	  MD5_CTX md5_ctx;
	  MD5_Init(&md5_ctx);
	  MD5_Update(&md5_ctx, buffer, strlen(buffer));
	  MD5_Final(hash, &md5_ctx);
	

	time_t end = time(NULL);
	printf("Execution took ~%fs\n", difftime(end, start));
	return 0;
}


Ich denke, wenn ich den vorgegeben Code, bzw. die vorgegeben Arrays bzw. Variablen richtig verstehe wofür genau ich die brauche, würde mir das enorm weiterhelfen. Im Moment bin ich ziemlich ratlos.
Auch habe ich nicht wirklich eine Ahnung, wie man die Wörter des Textes überhaupt einlesen kann.

So wie ich den Rest des vorgegeben Codes verstehe, ist im Prinzip der 3. und 4. Teil der Aufgabe schon vorgegeben, sodass es im Prinzip nur darum geht, die Wörter der Datei zu speichern.
Ich hoffe mir kann jemand weiterhelfen und schon mal vielen Dank im voraus. Im folgenden noch der Code für den MD5 hash, damit das Programm compiliert werden kann.

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
278:
279:
280:
281:
282:
283:
284:
285:
286:
287:
288:
289:
290:
291:
292:
293:
294:
295:
296:
297:
298:
/*
 * This is an OpenSSL-compatible implementation of the RSA Data Security, Inc.
 * MD5 Message-Digest Algorithm (RFC 1321).
 *
 * Homepage:
 * http://openwall.info/wiki/people/solar/software/public-domain-source-code/md5
 *
 * Author:
 * Alexander Peslyak, better known as Solar Designer <solar at openwall.com>
 *
 * This software was written by Alexander Peslyak in 2001.  No copyright is
 * claimed, and the software is hereby placed in the public domain.
 * In case this attempt to disclaim copyright and place the software in the
 * public domain is deemed null and void, then the software is
 * Copyright (c) 2001 Alexander Peslyak and it is hereby released to the
 * general public under the following terms:
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted.
 *
 * There's ABSOLUTELY NO WARRANTY, express or implied.
 *
 * (This is a heavily cut-down "BSD license".)
 *
 * This differs from Colin Plumb's older public domain implementation in that
 * no exactly 32-bit integer data type is required (any 32-bit or wider
 * unsigned integer data type will do), there's no compile-time endianness
 * configuration, and the function prototypes match OpenSSL's.  No code from
 * Colin Plumb's implementation has been reused; this comment merely compares
 * the properties of the two independent implementations.
 *
 * The primary goals of this implementation are portability and ease of use.
 * It is meant to be fast, but not as fast as possible.  Some known
 * optimizations are not included to reduce source code size and avoid
 * compile-time configuration.
 */

#ifndef HAVE_OPENSSL

#include <string.h>

#include "md5.h"

/*
 * The basic MD5 functions.
 *
 * F and G are optimized compared to their RFC 1321 definitions for
 * architectures that lack an AND-NOT instruction, just like in Colin Plumb's
 * implementation.
 */
#define F(x, y, z)			((z) ^ ((x) & ((y) ^ (z))))
#define G(x, y, z)			((y) ^ ((z) & ((x) ^ (y))))
#define H(x, y, z)			(((x) ^ (y)) ^ (z))
#define H2(x, y, z)			((x) ^ ((y) ^ (z)))
#define I(x, y, z)			((y) ^ ((x) | ~(z)))

/*
 * The MD5 transformation for all four rounds.
 */
#define STEP(f, a, b, c, d, x, t, s) \
	(a) += f((b), (c), (d)) + (x) + (t); \
	(a) = (((a) << (s)) | (((a) & 0xffffffff) >> (32 - (s)))); \
	(a) += (b);

/*
 * SET reads 4 input bytes in little-endian byte order and stores them
 * in a properly aligned word in host byte order.
 *
 * The check for little-endian architectures that tolerate unaligned
 * memory accesses is just an optimization.  Nothing will break if it
 * doesn't work.
 */
#if defined(__i386__) || defined(__x86_64__) || defined(__vax__)
#define SET(n) \
	(*(MD5_u32plus *)&ptr[(n) * 4])
#define GET(n) \
	SET(n)
#else
#define SET(n) \
	(ctx->block[(n)] = \
	(MD5_u32plus)ptr[(n) * 4] | \
	((MD5_u32plus)ptr[(n) * 4 + 1] << 8) | \
	((MD5_u32plus)ptr[(n) * 4 + 2] << 16) | \
	((MD5_u32plus)ptr[(n) * 4 + 3] << 24))
#define GET(n) \
	(ctx->block[(n)])
#endif

/*
 * This processes one or more 64-byte data blocks, but does NOT update
 * the bit counters.  There are no alignment requirements.
 */
static const void *body(MD5_CTX *ctx, const void *data, unsigned long size)
{
	const unsigned char *ptr;
	MD5_u32plus a, b, c, d;
	MD5_u32plus saved_a, saved_b, saved_c, saved_d;

	ptr = (const unsigned char *)data;

	a = ctx->a;
	b = ctx->b;
	c = ctx->c;
	d = ctx->d;

	do {
		saved_a = a;
		saved_b = b;
		saved_c = c;
		saved_d = d;

/* Round 1 */
		STEP(F, a, b, c, d, SET(0), 0xd76aa478, 7)
		STEP(F, d, a, b, c, SET(1), 0xe8c7b756, 12)
		STEP(F, c, d, a, b, SET(2), 0x242070db, 17)
		STEP(F, b, c, d, a, SET(3), 0xc1bdceee, 22)
		STEP(F, a, b, c, d, SET(4), 0xf57c0faf, 7)
		STEP(F, d, a, b, c, SET(5), 0x4787c62a, 12)
		STEP(F, c, d, a, b, SET(6), 0xa8304613, 17)
		STEP(F, b, c, d, a, SET(7), 0xfd469501, 22)
		STEP(F, a, b, c, d, SET(8), 0x698098d8, 7)
		STEP(F, d, a, b, c, SET(9), 0x8b44f7af, 12)
		STEP(F, c, d, a, b, SET(10), 0xffff5bb1, 17)
		STEP(F, b, c, d, a, SET(11), 0x895cd7be, 22)
		STEP(F, a, b, c, d, SET(12), 0x6b901122, 7)
		STEP(F, d, a, b, c, SET(13), 0xfd987193, 12)
		STEP(F, c, d, a, b, SET(14), 0xa679438e, 17)
		STEP(F, b, c, d, a, SET(15), 0x49b40821, 22)

/* Round 2 */
		STEP(G, a, b, c, d, GET(1), 0xf61e2562, 5)
		STEP(G, d, a, b, c, GET(6), 0xc040b340, 9)
		STEP(G, c, d, a, b, GET(11), 0x265e5a51, 14)
		STEP(G, b, c, d, a, GET(0), 0xe9b6c7aa, 20)
		STEP(G, a, b, c, d, GET(5), 0xd62f105d, 5)
		STEP(G, d, a, b, c, GET(10), 0x02441453, 9)
		STEP(G, c, d, a, b, GET(15), 0xd8a1e681, 14)
		STEP(G, b, c, d, a, GET(4), 0xe7d3fbc8, 20)
		STEP(G, a, b, c, d, GET(9), 0x21e1cde6, 5)
		STEP(G, d, a, b, c, GET(14), 0xc33707d6, 9)
		STEP(G, c, d, a, b, GET(3), 0xf4d50d87, 14)
		STEP(G, b, c, d, a, GET(8), 0x455a14ed, 20)
		STEP(G, a, b, c, d, GET(13), 0xa9e3e905, 5)
		STEP(G, d, a, b, c, GET(2), 0xfcefa3f8, 9)
		STEP(G, c, d, a, b, GET(7), 0x676f02d9, 14)
		STEP(G, b, c, d, a, GET(12), 0x8d2a4c8a, 20)

/* Round 3 */
		STEP(H, a, b, c, d, GET(5), 0xfffa3942, 4)
		STEP(H2, d, a, b, c, GET(8), 0x8771f681, 11)
		STEP(H, c, d, a, b, GET(11), 0x6d9d6122, 16)
		STEP(H2, b, c, d, a, GET(14), 0xfde5380c, 23)
		STEP(H, a, b, c, d, GET(1), 0xa4beea44, 4)
		STEP(H2, d, a, b, c, GET(4), 0x4bdecfa9, 11)
		STEP(H, c, d, a, b, GET(7), 0xf6bb4b60, 16)
		STEP(H2, b, c, d, a, GET(10), 0xbebfbc70, 23)
		STEP(H, a, b, c, d, GET(13), 0x289b7ec6, 4)
		STEP(H2, d, a, b, c, GET(0), 0xeaa127fa, 11)
		STEP(H, c, d, a, b, GET(3), 0xd4ef3085, 16)
		STEP(H2, b, c, d, a, GET(6), 0x04881d05, 23)
		STEP(H, a, b, c, d, GET(9), 0xd9d4d039, 4)
		STEP(H2, d, a, b, c, GET(12), 0xe6db99e5, 11)
		STEP(H, c, d, a, b, GET(15), 0x1fa27cf8, 16)
		STEP(H2, b, c, d, a, GET(2), 0xc4ac5665, 23)

/* Round 4 */
		STEP(I, a, b, c, d, GET(0), 0xf4292244, 6)
		STEP(I, d, a, b, c, GET(7), 0x432aff97, 10)
		STEP(I, c, d, a, b, GET(14), 0xab9423a7, 15)
		STEP(I, b, c, d, a, GET(5), 0xfc93a039, 21)
		STEP(I, a, b, c, d, GET(12), 0x655b59c3, 6)
		STEP(I, d, a, b, c, GET(3), 0x8f0ccc92, 10)
		STEP(I, c, d, a, b, GET(10), 0xffeff47d, 15)
		STEP(I, b, c, d, a, GET(1), 0x85845dd1, 21)
		STEP(I, a, b, c, d, GET(8), 0x6fa87e4f, 6)
		STEP(I, d, a, b, c, GET(15), 0xfe2ce6e0, 10)
		STEP(I, c, d, a, b, GET(6), 0xa3014314, 15)
		STEP(I, b, c, d, a, GET(13), 0x4e0811a1, 21)
		STEP(I, a, b, c, d, GET(4), 0xf7537e82, 6)
		STEP(I, d, a, b, c, GET(11), 0xbd3af235, 10)
		STEP(I, c, d, a, b, GET(2), 0x2ad7d2bb, 15)
		STEP(I, b, c, d, a, GET(9), 0xeb86d391, 21)

		a += saved_a;
		b += saved_b;
		c += saved_c;
		d += saved_d;

		ptr += 64;
	} while (size -= 64);

	ctx->a = a;
	ctx->b = b;
	ctx->c = c;
	ctx->d = d;

	return ptr;
}

void MD5_Init(MD5_CTX *ctx)
{
	ctx->a = 0x67452301;
	ctx->b = 0xefcdab89;
	ctx->c = 0x98badcfe;
	ctx->d = 0x10325476;

	ctx->lo = 0;
	ctx->hi = 0;
}

void MD5_Update(MD5_CTX *ctx, const void *data, unsigned long size)
{
	MD5_u32plus saved_lo;
	unsigned long used, available;

	saved_lo = ctx->lo;
	if ((ctx->lo = (saved_lo + size) & 0x1fffffff) < saved_lo)
		ctx->hi++;
	ctx->hi += size >> 29;

	used = saved_lo & 0x3f;

	if (used) {
		available = 64 - used;

		if (size < available) {
			memcpy(&ctx->buffer[used], data, size);
			return;
		}

		memcpy(&ctx->buffer[used], data, available);
		data = (const unsigned char *)data + available;
		size -= available;
		body(ctx, ctx->buffer, 64);
	}

	if (size >= 64) {
		data = body(ctx, data, size & ~(unsigned long)0x3f);
		size &= 0x3f;
	}

	memcpy(ctx->buffer, data, size);
}

void MD5_Final(unsigned char *result, MD5_CTX *ctx)
{
	unsigned long used, available;

	used = ctx->lo & 0x3f;

	ctx->buffer[used++] = 0x80;

	available = 64 - used;

	if (available < 8) {
		memset(&ctx->buffer[used], 0, available);
		body(ctx, ctx->buffer, 64);
		used = 0;
		available = 64;
	}

	memset(&ctx->buffer[used], 0, available - 8);

	ctx->lo <<= 3;
	ctx->buffer[56] = ctx->lo;
	ctx->buffer[57] = ctx->lo >> 8;
	ctx->buffer[58] = ctx->lo >> 16;
	ctx->buffer[59] = ctx->lo >> 24;
	ctx->buffer[60] = ctx->hi;
	ctx->buffer[61] = ctx->hi >> 8;
	ctx->buffer[62] = ctx->hi >> 16;
	ctx->buffer[63] = ctx->hi >> 24;

	body(ctx, ctx->buffer, 64);

	result[0] = ctx->a;
	result[1] = ctx->a >> 8;
	result[2] = ctx->a >> 16;
	result[3] = ctx->a >> 24;
	result[4] = ctx->b;
	result[5] = ctx->b >> 8;
	result[6] = ctx->b >> 16;
	result[7] = ctx->b >> 24;
	result[8] = ctx->c;
	result[9] = ctx->c >> 8;
	result[10] = ctx->c >> 16;
	result[11] = ctx->c >> 24;
	result[12] = ctx->d;
	result[13] = ctx->d >> 8;
	result[14] = ctx->d >> 16;
	result[15] = ctx->d >> 24;

	memset(ctx, 0, sizeof(*ctx));
}

#endif

hier die md5.h Datei
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
/*
 * This is an OpenSSL-compatible implementation of the RSA Data Security, Inc.
 * MD5 Message-Digest Algorithm (RFC 1321).
 *
 * Homepage:
 * http://openwall.info/wiki/people/solar/software/public-domain-source-code/md5
 *
 * Author:
 * Alexander Peslyak, better known as Solar Designer <solar at openwall.com>
 *
 * This software was written by Alexander Peslyak in 2001.  No copyright is
 * claimed, and the software is hereby placed in the public domain.
 * In case this attempt to disclaim copyright and place the software in the
 * public domain is deemed null and void, then the software is
 * Copyright (c) 2001 Alexander Peslyak and it is hereby released to the
 * general public under the following terms:
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted.
 *
 * There's ABSOLUTELY NO WARRANTY, express or implied.
 *
 * See md5.c for more information.
 */

#ifdef HAVE_OPENSSL
#include <openssl/md5.h>
#elif !defined(_MD5_H)
#define _MD5_H

/* Any 32-bit or wider unsigned integer data type will do */
typedef unsigned int MD5_u32plus;

typedef struct {
	MD5_u32plus lo, hi;
	MD5_u32plus a, b, c, d;
	unsigned char buffer[64];
	MD5_u32plus block[16];
} MD5_CTX;

extern void MD5_Init(MD5_CTX *ctx);
extern void MD5_Update(MD5_CTX *ctx, const void *data, unsigned long size);
extern void MD5_Final(unsigned char *result, MD5_CTX *ctx);

#endif
 
Auf diesen Beitrag antworten »
eulerscheZahl

Hashfunktion: eine beliebig lange Bytefolge soll auf eine bestimmte Länge reduziert werden und gleichzeitig ein identischer Hashwert für ähnliche Bytefolgen möglichst ausgeschlossen werden. Wenn du z.B. eine große Datei aus dem Internet lädtst, kannst du so sicherstellen, dass sie auch fehlerfrei bei dir angekommen ist. Daher wird der Hash der Datei manchmal angegeben (siehe eclipse).

Du sollst letztlich die Hashfunktion umkehren, also einen string finden, dessen hash target entspricht. Man kann aus Hashwerten aber nicht direkt das Original errechnen: zum einen gibt es mehr als eine Möglichkeit, auf einen bestimmten Hashwert zu kommen (der ja eine begrenzte Größe hat, während das Original größer sein kann), zum anderen wird oft großer Aufwand betrieben, die Funktion derart zu gestalten, dass sie sich nicht invertieren lässt (wichtig für Kryptographie, in deinem Fall eher uninteressant).

Deshalb sollst du sämtliche Kombinationen mit dem vorgegebenen Hash vergleichen.

Ich verstehe ehrlich gesagt nicht, wie du so Wörter einlesen willst, hier mal mein Vorschlag:
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
char* words[100]; //100 Wörter können gespeichert werden
char c;
char str[1024]; //aktuelles Wort
int letterCount = 0; //Anzahl der Buchstaben im aktuellen Wort
int wordCount = 0; //Anzahl der Wörter
while ((c = fgetc(f)) != EOF) {
	char needle[2] = {c};
	if (!strstr(delim, needle)) {
		str[letterCount++] = c;
	} else {
		str[letterCount++] = '\0';
		if (letterCount > 1) {
			char* tmp;
			if ((tmp = malloc(letterCount * sizeof(char))) == NULL) return -1;
			strncpy(tmp, str, letterCount);
			words[wordCount++] = tmp;
		}
		letterCount = 0; 
	}
}
for (int i = 0; i < wordCount; i++) {
	printf("%s\n", words[i]);
}
Auf diesen Beitrag antworten »
as_string

Also, irgendetwas passt da bei der Aufgabenstellung nicht zusammen...

Einerseits schreibst Du, dass die Aufgabe wohl sei, eine eindeutige Liste von vorkommenden Wörtern zu generieren. Dazu muss man wohl auch eine Hashtabelle aufbauen, so dass der Lookup relativ schnell ist. Warum man dafür MD5 verwenden sollte, der ja eigentlich eher kryptographische Zwecke erfüllt als besonders schnell zu sein um ihn bei Hash-Tabellen zu verwenden, ist mir nicht klar.
Des weitern hat eulerscheZahl natürlich Recht, dass wohl auch ein String gefunden werden soll, der dem vorgegebenen target-Hash entspricht. Nur was soll das wiederum mit der Liste eindeutiger Wörter zu tun haben?
Die erste Teilaufgabe, die im Quelltext genannt ist, ist die eindeutige Wortliste... ok. Dann ist aber die Rede von "two-string combinations". Hä? Welche zwei Strings? Die von zwei Wörtern? Sprich, man soll die eindeutige Liste nehmen und jedes Wort mit allen anderen kombinieren und mit der Kombination einen Hash bilden? Für was soll das denn gut sein? Soll man dann die Kombination finden, die dem Target-Hash entspricht oder wie? Keine Ahnung...

Also eine etwas genauere Aufgabenstellung braucht man da mE schon. Gibt es da einen noch einen Aufgabentext dazu, den Du uns im Original geben könntest?

So wie ich die Aufgabe verstehe: Ersteinmal eine eindeutige Liste der vorkommenden Wörter bilden. Das macht man normalerweise mit einer Hash-Tabelle und mit einer für Strings passenden Hash-Funktion. Ich würde da nicht MD5 dafür nehmen. Um das Leben einfach zu gestalten, würde ich noch eine verkettete Liste führen, damit man die Hashtabelle am Ende auch vernünftig ausgelesen bekommt. Ob man diesen Teil parallelisieren kann ist mE fraglich und würde auch nicht viel bringen, weil dabei ja auch noch die Datei gelesen wird, so dass das Eintragen in die Hash-Tabelle wohl die geringste Zeit kosten wird.
Wenn das mit Hash-Tabelle zu kompliziert ist: Man kann erst eine Liste machen, in der man sich alle Wörter merkt, wie sie vorkommen und diese dann anschließend sortieren. Dann läuft man über die Liste und nutzt aus, dass nach der Sortierung ja logischerweise alle gleichen Wörter hintereinander kommen, so dass man recht leicht eine eindeutige Liste bekommt.
Das ist auch sehr ungeschickt, weil man dann wirklich den ganzen Text im Speicher halten muss und dazu noch im Anschluss sortieren muss. Der Ansatz mit der Hashtabelle ist da viel effizienter, aber auch etwas aufwändiger umzusetzen, denke ich.

Wenn man diese Liste hat, muss man offenbar Wortpaare bilden, für jedes Paar einen Hash berechnen und den mit dem target vergleichen. Das ist der Teil, den man gut parallelisieren kann, denke ich. Vielleicht machst Du eine Funktion, die die beiden Indizes der beiden zu kombinierenden Wörter in der eindeutigen Liste als Parameter bekommt und einen Hashwert zurück gibt. Dann vergleichst Du diesen Wert mit dem target. Das kannst Du natürlich für alle Paare parallel machen, also das Ausrechnen des Hash und das Vergleichen.

Außerdem: Du musst bei MD5 die beiden Teilstrings nicht erst Concatinieren, man kann auch einfach zweimal MD5_Update() aufrufen, also einmal den Init, zweimal das Update und dann das Finalize, um den fertigen MD5 zu bekommen.

Noch was wegen der HASH_LENGTH-Konstante: Die Länge eines MD5-Hashwertes ist immer 16 Byte.

Gruß
Marco
Auf diesen Beitrag antworten »
deppensido

hallo,

erst mal danke für die Antworten. So, wie ich das jetzt verstanden habe, muss ich den Hash der eingelesen Wörter mit den Hashwerten von target vergleichen. Der Hash eines eingelesen Wortes wird ja mit MD5_Final übergeben, sodass dieser im Array "hash" stehen müsste (da dies ja an MD5_Final übergeben wird), somit habe ich versucht einfach den jeweils eingelesenen Hash-Wert von hash nach jedem eingelesen Wort mit target zu vergleichen und anschließend das jeweilige Wort auszugeben. Komischerweise kommt bei Ausführung immer SIGSEV oder so ähnlich und das Programm bricht ab, kompilieren tut es aber. Nach Aufgabenstellung ist es glaube ich nicht schlimm, wenn gleiche Wörter mehrfach eingelesen werden, da steht ja nur "Alle Wörter die mindestens einmal im Text vorkommen abspeichern". Nach dem Hinweis von "as_string" rufe ich die Funktion MD5_Update 2 mal auf. Die Arraygröße von "words" habe ich auf 1 Million erhöht, da der Text "Les Miserables" ungefähr so viele Wörter enthält und sonst nicht eingelesen werden könnte. Ist meine Gedankenweise so erst mal richtig oder ist die komplett daneben? Vielen Dank schon mal im voraus. Im folgenden noch der Code:
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
// You can use these includes and defines as a hint what functions you might want to use ;)
#define _GNU_SOURCE
#include "md5.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <omp.h>
#include <time.h>

#define HASH_LENGTH 16  

int main (){
  
	//Bis zur Aufgabenstellung ist dieser Teil des Codes vorgegeben gewesen
	// unsigned char target[HASH_LENGTH] = {0xe6, 0x54, 0x93, 0xcc, 0xde, 0xe9, 0xc4, 0x51, 0x4f, 0xe2, 0x0e, 0x04, 0x04, 0xf3, 0xbc, 0xb8}; //"???" - to be used for les_miserables.txt
	unsigned char target[HASH_LENGTH] = {0x1c, 0x01, 0x43, 0xc6, 0xac, 0x75, 0x05, 0xc8, 0x86, 0x6d, 0x10, 0x27, 0x0a, 0x48, 0x0d, 0xec}; // "Les Miserables" - to be used for les_miserables_preface.txt
	time_t start = time(NULL);
	FILE* f;
	f = fopen("les_miserables_preface.txt", "r");
	
	if(f == NULL){
		return 1;
	}
	const char* delim = " .,;-:0123456789?!\"*+()|&[]#$/%%'"; 
	unsigned char hash[HASH_LENGTH] = {0};
	
	
	//Dies ist die Aufgabenstellung
	/*
	 * - find all unique words from the book
	 * - create the hashes of all two-string combinations
	 * - try to speed it up
	 * Usage example (not complete!):
	 */ 
	
	  MD5_CTX md5_ctx;
	 
	  char* words[1000000]; //1 Million Wörter können gespeichert werden
	  char c;
	  char buffer[1024]; //aktuelles Wort
	  int letterCount = 0; //Anzahl der Buchstaben im aktuellen Wort
	  int wordCount = 0; //Anzahl der Wörter
	  int match = 0;
	  while ((c = fgetc(f)) != EOF) {
	      char needle[2] = {c};
	    if (!strstr(delim, needle)) {
		buffer[letterCount++] = c;
	    } else {
		buffer[letterCount++] = '\0';
		if (letterCount > 1) {
			char* tmp;
			if ((tmp = malloc(letterCount * sizeof(char))) == NULL) return -1;
			strncpy(tmp, buffer, letterCount);
			words[wordCount++] = tmp;
		}
		letterCount = 0; 
		//nach String-Kombination mit Hilfe von MD5 suchen
		MD5_Init(&md5_ctx);
		MD5_Update(&md5_ctx, buffer, strlen(buffer));
		MD5_Update(&md5_ctx, buffer, strlen(buffer));
		MD5_Final(hash, &md5_ctx);
		int i,j;
		for(i=0;i<HASH_LENGTH;i++)
		  for(j=0;j<HASH_LENGTH;j++)
		    if(hash[i]==target[j]) {
		      match = 1;
		      printf("%s\n",words[wordCount]);
		    }
	      }
	  }
	  /*
	  int i;
	  for (i = 0; i < wordCount; i++) {
		printf("%s\n", words[i]);
	  }
	  */
	      if(match == 0)
		printf("nichts gefunden\n");
//Der Rest des Codes war vorgegeben
	time_t end = time(NULL);
	printf("Execution took ~%fs\n", difftime(end, start));
	return 0;
}
 
Auf diesen Beitrag antworten »
as_string

Hallo!

Ich habe gerade keine Zeit, aber was mir auf den aller ersten Blick auffällt:

code:
1:
2:
3:
4:
5:
6:
7:
8:
		for(i=0;i<HASH_LENGTH;i++)
		  for(j=0;j<HASH_LENGTH;j++)
		    if(hash[i]==target[j]) {
		      match = 1;
		      printf("%s\n",words[wordCount]);
		    }

Das ist ja in mehrfacher Hinsicht falsch: Du willst, dass Byte i von hash gleich Byte i von target ist, nicht dass jedes Byte von hash mit jedem in target übereinstimmt. Du brauchst keine verschachtelten for-Schleifen sondern nur einmal über die Hash-Länge laufen dafür!
Außerdem setzt Du match bei jedem einzelnen Treffer auf 1 und gibst den Text aus. Du willst aber nur dann, wenn alle Bytes mit dem selben Index in den beiden Arrays übereinstimmen einmal sagen, dass alles "match"t.
Ich würde deshalb zuerst match auf 1 und i auf 0 setzen. Dann eine while-Schleife machen, die so lange weiter geht, wie (match && i < HASH_LENGTH) ist. Dann die beiden Elemente der beiden Arrays an der Stelle i vergleichen. Wenn verschieden match auf 0 setzen, danach i hoch zählen und die Schleife ist fertig.

Den Rest muss ich mir andersmal anschauen. Dein Fehler ist übrigens ein SEGFAULT (SIGSEGV) und tritt auf, wenn Du versuchst auf Speicher zuzugreifen, den Du noch nicht oder nicht mehr reserviert hast. Häufig, wenn z. B. ein Zeiger noch nicht initialisiert ist oder wenn Du auf ein Array außerhalb der reservierten Arraygröße versuchst zuzugreifen (out-of-bounds), oder auch, wenn eine Speicherreservierung nicht geklappt hat man trotzdem munter drauf zuzugreifen versucht, oder irgendwo einen null-pointer her hat, den man versucht zu dereferenzieren, oder oder oder...
Da muss ich andersmal danach suchen dann.

Gruß
Marco
Auf diesen Beitrag antworten »
as_string

Ich glaube, dass auch das mit dem strstr und dem needle die Probleme machen könnte. Muss needle nicht ein zero-terminated string sein? Dann sollte man
code:
1:
char needle[2] = {c, '\0'};

scheiben, oder nicht?

Gruß
Marco
Auf diesen Beitrag antworten »
eulerscheZahl

Zitat:
Nach Aufgabenstellung ist es glaube ich nicht schlimm, wenn gleiche Wörter mehrfach eingelesen werden, da steht ja nur "Alle Wörter die mindestens einmal im Text vorkommen abspeichern"

Da werden dann eben aus 50.000 Wörtern plötzlich 500.000. Da du immer Paare aus zwei Wörtern bilden sollst, hast du eine quadratische Laufzeit, also brauchst du 100 mal so lange. Da es bei mir auch so schon eine halbe Stunde dauert, solltest du die Auswahl so weit wie möglich einschränken.

Die Lösung ist übrigens "threads help".
Auf diesen Beitrag antworten »
deppensido

ich habe den Code entsprechend der Beschreibung von Marco nun folgendermaßen abgeändert.
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
 char* words[1000000]; //1 Million Wörter können gespeichert werden
	  char c;
	  char buffer[1024]; //aktuelles Wort
	  int letterCount = 0; //Anzahl der Buchstaben im aktuellen Wort
	  int wordCount = 0; //Anzahl der Wörter
	  int match = 1;
	  while ((c = fgetc(f)) != EOF) {
	      char needle[2] = {c, '\0'};
	    if (!strstr(delim, needle)) {
		buffer[letterCount++] = c;
	    } else {
		buffer[letterCount++] = '\0';
		if (letterCount > 1) {
			char* tmp;
			if ((tmp = malloc(letterCount * sizeof(char))) == NULL) return -1;
			strncpy(tmp, buffer, letterCount);
			words[wordCount++] = tmp;
		}
		letterCount = 0; 
		//nach String-Kombination mit Hilfe von MD5 suchen
		
		MD5_Init(&md5_ctx);
		MD5_Update(&md5_ctx, buffer, strlen(buffer));
		MD5_Update(&md5_ctx, buffer, strlen(buffer));
		MD5_Final(hash, &md5_ctx);
		//words = (char* [1000000])malloc(sizeof(1000000));//Das klappt irgendwie nicht
		int i;
		while(match && i < HASH_LENGTH) {
		     if(hash[i] == target[i]) 
			  printf("%s\n",hash[i]);
		     else 
			 match = 0;
		     i++;
		}
	    }
	  }


Irgendwie passt das ganze aber überhaupt noch nicht. Das Programm läuft nahezu ohne Verzögerung, auch mit der großen Textdatei und die Werte von hash[i], wie auch von target[i] sind alle NULL.
Also ich denke, da fehlt noch eine ganze Menge traurig
Auf diesen Beitrag antworten »
eulerscheZahl

Ich sehe nicht, dass du irgendetwas sinnvolles (also 2 Wörter) an MD5_Update übergibst. Dafür brauchst du 2 verschachtelte Schleifen.

Ach ja: char needle[2] = {c} Füllt alles außer das erste Arrayelement mit 0 auf, was ja '\0' entspricht.

Ich habe das mal mit C# durchprobiert (damit bin ich einfach schneller):
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
static void Main(string[] args) {
	string path = "/home/eulerschezahl/Dokumente/Programmieren/C_C++/infoboard/les_miserables_preface.txt";
	string text = File.ReadAllText (path);
	string[] words = text.Split (" .,;-:0123456789?!\"*+()|&[]#$/\\%'".ToCharArray (), StringSplitOptions.RemoveEmptyEntries);
	words = words.Distinct ().ToArray ();
	MD5 md5 = new MD5Cng ();
	for(int i = 0; i< words.Length; i++) {
		for(int j = 0; j< words.Length; j++) {

			string test = words [i] + " " + words [j];
			byte[] b = new byte[test.Length];
			for (int k = 0; k < b.Length; k++) {
				b [k] = (byte)test [k];
			}
			byte[] target = {0xe6, 0x54, 0x93, 0xcc, 0xde, 0xe9, 0xc4, 0x51, 0x4f, 0xe2, 0x0e, 0x04, 0x04, 0xf3, 0xbc, 0xb8};
			byte[] hash = md5.ComputeHash (b);
			if (Enumerable.Range(0,16).Count(x => target[x] != hash[x]) == 0)
				Console.WriteLine(test); //threads help
		}
	}
}
Auf diesen Beitrag antworten »
as_string

Hallo!

Oh, stimmt... Das war mir nicht bewusst, dass C den Rest dann mit Nullen auffüllt. Schon wieder was dazu gelernt!

Gruß
Marco
Auf diesen Beitrag antworten »
deppensido

also folgendes ist nun doch das beste was mir eingefallen ist: Der Code beginnt erst nach der while Schleife, die die Wörter aus der Datei einliest:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
MD5_Init(&md5_ctx);
		int i,j,k;
		for(i=0;i<wordCount;i++) {
		  for(j=0;j<wordCount;j++) {
			MD5_Update(&md5_ctx, words[i], strlen(words[i]));
			MD5_Update(&md5_ctx, words[j], strlen(words[j]));
			MD5_Final(hash, &md5_ctx);
			for(k=0; k < HASH_LENGTH; k++) {
			    if((target[k] != hash[k]) == 0)
			      printf("%s %s\n", words[i], words[j]);
			}
		  } 
		}

basierend darauf, dass ich 2 verschachtelte Schleifen für MD5_Update brauche und da ich mich etwas nach dem C# Code orientiert habe. Wäre das mit dem testen aller möglichen 2er Kombinationen per MD5 so erstmal korrekt? Ich bin mir jetzt nicht sicher, ob auch Steuerzeichen mit abgespeichert werden, das darf nach Punkt 2 der Aufgabenstellung ja nicht passieren und man soll anhand eines vorgegeben Hashwertes noch die beiden dazugehörigen Wörter finden. Vielen Dank schon mal.
Auf diesen Beitrag antworten »
deppensido

Es darf doch nur jedes Wort, das mindestens einmal im Text vorkommt nur je einmal abgespeichert werden. In der Aufgabenstellung vom vorgegeben Code steht: "find all unique words from the book". Somit ist das doch eindeutig und wie ich gerade sehe, ist die Laufzeit sonst viel zu lang.

Kann ich das mit der Funktion "strtok()" und dem gegebenen delimiter erreichen? Dies wird in Punkt 2 der Aufgabe ja auch als Hinweis angegeben.
Auf diesen Beitrag antworten »
deppensido

so nachdem ich die ganze Nacht daran gesessen habe, habe ich nun folgendes:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
// You can use these includes and defines as a hint what functions you might want to use ;)
#define _GNU_SOURCE
#include "md5.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <omp.h>
#include <time.h>

#define HASH_LENGTH 16  

int main (){
  
	//Bis zur Aufgabenstellung ist dieser Teil des Codes vorgegeben gewesen
	//unsigned char target[HASH_LENGTH] = {0xe6, 0x54, 0x93, 0xcc, 0xde, 0xe9, 0xc4, 0x51, 0x4f, 0xe2, 0x0e, 0x04, 0x04, 0xf3, 0xbc, 0xb8}; //"???" - to be used for les_miserables.txt
	unsigned char target[HASH_LENGTH] = {0x1c, 0x01, 0x43, 0xc6, 0xac, 0x75, 0x05, 0xc8, 0x86, 0x6d, 0x10, 0x27, 0x0a, 0x48, 0x0d, 0xec}; // "Les Miserables" - to be used for les_miserables_preface.txt
	time_t start = time(NULL);
	FILE* f;
	f = fopen("les_miserables_preface.txt", "r");
	
	if(f == NULL){
		return 1;
	}
	const char* delim = " .,;-:0123456789?!\"*+()|&[]#$/%%' \n \t"; 
	unsigned char hash[HASH_LENGTH] = {0};
	
	
	//Dies ist die Aufgabenstellung
	/*
	 * - find all unique words from the book
	 * - create the hashes of all two-string combinations
	 * - try to speed it up
	 * Usage example (not complete!):
	 */ 
	  char* words[1000000]; //1 Million Wörter können gespeichert werden
	  char c;
	  char buffer[1024]; //aktuelles Wort
	  int letterCount = 0; //Anzahl der Buchstaben im aktuellen Wort
	  int wordCount = 0; //Anzahl der Wörter
	  
	  while ((c = fgetc(f)) != EOF) {
	      char needle[2] = {c};
	    if (!strstr(delim, needle)) {
		buffer[letterCount++] = c;
	    } else {
		buffer[letterCount++] = '\0';
		if (letterCount > 1) {
			char* tmp;
			if ((tmp = malloc(letterCount * sizeof(char))) == NULL) return -1;
			strncpy(tmp, buffer, letterCount);
			//hier optimieren per OpenMP
			int i = 0;
			int match = 0;
			while(i < wordCount) {
			    if(strcmp(tmp, words[i]) == 0) {
				match = 1;
				i = wordCount;
			    }
			    else  i++;
			}
			if(match == 0) {
			    words[wordCount] = tmp;
			    wordCount++;
			}
			//bis hier optimieren
		}
		letterCount = 0;  
	    }
	  }
	  //nach String-Kombination mit Hilfe von MD5 suchen
		//hier optimieren per OpenMP
		MD5_CTX md5_ctx;
		MD5_Init(&md5_ctx);
		int i,j,k;
		for(i=0;i<wordCount;i++) {
		  for(j=0;j<wordCount;j++) {
			MD5_Update(&md5_ctx, words[i], strlen(words[i]));
			MD5_Update(&md5_ctx, " ", strlen(" "));
			MD5_Update(&md5_ctx, words[j], strlen(words[j]));
			MD5_Final(hash, &md5_ctx);
			for(k=0; k < HASH_LENGTH; k++) {
			      if((target[k] != hash[k]) == 0) {
				  printf("%s %s %x\n", words[i], words[j], hash[k]);
			      }
			}
		  } 
		}
		//bis hier optimieren
		
//Der Rest des Codes war vorgegeben
	time_t end = time(NULL);
	printf("Execution took ~%fs\n", difftime(end, start));
	return 0;
}

die Stellen die ich noch optimieren will, habe ich kommentiert. Aber was immer mir noch nicht klar ist, wie ich nach Aufgabenstellung, Wörter zu einem Hash finden soll. Der Hash zu dem man die zwei Wörter finden soll ist 32 Zeichen lang, bei der Ausgabe, ist der dazugehörige Hash aber nur höchstens 2 Zeichen lang. Hab ich da was falsch, oder passt die Aufgabenstellung nun nicht? Mehr was ich da noch probieren könnte, fällt mir wirklich nicht mehr ein.

Dass die Wörter nur einmal eingelesen werden sollen, hab ich hinbekommen, wenn auch vielleicht etwas ungeschickt. Somit hat sich der Post zuvor erst mal erledigt.
Auf diesen Beitrag antworten »
as_string

Das hier ergibt keinen Sinn:

code:
1:
2:
3:
4:
5:
6:
			for(k=0; k < HASH_LENGTH; k++) {
			      if((target[k] != hash[k]) == 0) {
				  printf("%s %s %x\n", words[i], words[j], hash[k]);
			      }
			}

Was Du willst ist doch: Vergleiche jedes Element von target mit dem entsprechenden Element von hash. Wenn es (mindestens) eines gibt, das unterschiedlichen Wert hat, dann ist es kein Treffer, wenn alle übereinstimmen ist es ein Treffer.
Um diese Aussage treffen zu können musst Du doch dann aber logischerweise zuerst über die Arrays gelaufen sein und erst, wenn Du komplett ohne Unterschied durch gekommen bist, kannst Du etwas ausgeben.
Dann die Bedingung: Wenn etwas in C gleich 0 ist, entspricht es false. Dein if((...) == 0) wird also immer genau dann true, wenn das in der der Klammer false ist. Es wirkt also wie ein "not". Da Du in der Klammer auf Ungleichheit prüfst, aber das Ergebnis negierst, hast Du das selbe, wie wenn Du
code:
1:
if(target[k] == hash[k]) {...}

geschrieben hättest. Das ist aber hier so wie so Quatsch.

Übrigens, als Du die while-Schleife hattest, hast Du nicht die Variablen vorher initialisiert gehabt, so wie ich Dir das sogar geschrieben hatte: Natürlich musst Du die Zählvariable bei einer while()-Schleife vor der Schleife immer wieder auf 0 setzen. Außerdem musst Du die boolsche Variable auf 1 setzen.
Wenn Du aber keine while()-Schleife verwenden willst, geht das äquivalent auch mit einer for()-Schleife, etwa so:

code:
1:
2:
3:
4:
5:
6:
7:
for (k = 0, match = 1; (k < HASH_LENGTH) && match; k++) {
    if (target[k] != hash[k])
        match = 0;
}
if (match) { ... }


Hab das Fragment zwar jetzt nicht ausprobiert, sollte aber tun, was es soll.

Ein MD5-Hash ist immer 16 Byte lang. Wenn man die einzelnen Byte hexadezimal schreibt, bekommt man zwei Zeichen von 0-9 oder a-f für jedes Byte, also insgesamt 32. Ich weiß jetzt nicht, was Du mit 32 Zeichen meintest, allerdings.

So wie Du es geschrieben hattest, gibst Du aber immer nur übereinstimmende Bytes von hash aus, was, sorry..., Quatsch ist! Der ganze Hash muss übereinstimmen, oder er stimmt eben nicht überein. Ob einzelne Byte übereinstimmen wenn nicht all, ist irrelevant.

Um diesen Vergleich zu machen, brauchst Du aber eigentlich diese Schleife gar nicht selbst zu programmieren. Die C-Standardbibliothek hat schon fertige (und stark optimierte) Funktionen für solche Dinge. Z. B. :
code:
1:
2:
3:
4:
5:
6:
#include <string.h>
...

if (memcmp(target, hash, HASH_LENGTH) == 0) {...}

Das sollte auch funktionieren (auch völlig ungetestet von mir!). bei memcmp, strcmp und so ist wichtig: Die Funktionen geben -1, 0 oder 1 zurück. Bei Gleichheit eine 0.

Gruß
Marco
Auf diesen Beitrag antworten »
deppensido

hallo,

das funktioniert irgendwie nicht. Also jetzt wird überhaupt nichts mehr gefunden.

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
MD5_CTX md5_ctx;
		MD5_Init(&md5_ctx);
		int i,j;
		for(i=0;i<wordCount;i++) {
		  for(j=0;j<wordCount;j++) {
			MD5_Update(&md5_ctx, words[i], strlen(words[i]));
			MD5_Update(&md5_ctx, " ", strlen(" "));
			MD5_Update(&md5_ctx, words[j], strlen(words[j]));
			MD5_Final(hash, &md5_ctx);
			if (memcmp(target, hash, HASH_LENGTH) == 0) {
			      printf("%s %s\n", words[i], words[j]);
			}
		  } 
		}


bist du sicher, dass man das so machen muss?
Auf diesen Beitrag antworten »
deppensido

ich denke der Hash, der gefunden werden soll, wird nicht richtig richtig generiert
Auf diesen Beitrag antworten »
eulerscheZahl

Das init musst du innerhalb der Schleife machen, sonst hast du noch den alten Wert drin.
Auf diesen Beitrag antworten »
deppensido

ich versuch das mal eben.
Ich dachte erst, ich müsste die Wörter so in words einlesen, dass ich in words schon alle zweier String-Kombinationen habe. Ist aber immer ein SIGSEGV Signal gekommen. Versucht hatte ich das mit der Funktion strcat(). Nach Aufgabenblatt versteh ich das aber so, dass in words erstmal nur jedes Wort einzelnd gespeichert werden soll und das mit den 2er Strings dann über MD5 läuft. Welche Variante wäre denn nun die richtige?
Auf diesen Beitrag antworten »
deppensido

es scheint soweit jetzt zu klappen. Aber bei der Ausgabe des Hashwertes werden die Nullen nicht mit ausgegeben.
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
MD5_CTX md5_ctx;
		int i,j;
		for(i=0;i<wordCount;i++) {
		  for(j=0;j<wordCount;j++) {
			MD5_Init(&md5_ctx);
			MD5_Update(&md5_ctx, words[i], strlen(words[i]));
			MD5_Update(&md5_ctx," ", strlen(" "));
			MD5_Update(&md5_ctx, words[j], strlen(words[j]));
			MD5_Final(hash, &md5_ctx);
			if (memcmp(hash, target, HASH_LENGTH) == 0) {
			     printf("%s %s\n", words[i], words[j]);
			     printf("\n");
			     int k;
			     for(k=0;k<HASH_LENGTH;k++) {
				  if(hash[k]==' ')
				    printf("0");
				  printf("%x",hash[k]);
			     }
			     printf("\n");
			}
		  } 
		}

woran liegt das?
Auf diesen Beitrag antworten »
deppensido

ich habe die Aufgabe soweit fertig. Könnt ihr bitte nochmal schauen, ob ich die #pragma Anweisungen richtig gesetzt habe, damit das Programm schneller ausgeführt wird? Die Ausführung der großen Textdatei "Les Miserables.txt" dauert immer noch ca. 15 Minuten bis das Programm terminiert, das kann doch nicht richtig sein oder?

Hier noch der komplette Code, vielen Dank im voraus und schon mal danke für die bisherigen Hilfen.
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
// You can use these includes and defines as a hint what functions you might want to use ;)
#define _GNU_SOURCE
#include "md5.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <omp.h>
#include <time.h>

#define HASH_LENGTH 16  //da ein MD5-Hash 16 Byte groß ist

int main (){
  
	//unsigned char target[HASH_LENGTH] = {0xe6, 0x54, 0x93, 0xcc, 0xde, 0xe9, 0xc4, 0x51, 0x4f, 0xe2, 0x0e, 0x04, 0x04, 0xf3, 0xbc, 0xb8}; //"???" - to be used for les_miserables.txt
	unsigned char target[HASH_LENGTH] = {0x1c, 0x01, 0x43, 0xc6, 0xac, 0x75, 0x05, 0xc8, 0x86, 0x6d, 0x10, 0x27, 0x0a, 0x48, 0x0d, 0xec}; // "Les Miserables" - to be used for les_miserables_preface.txt
	time_t start = time(NULL);
	FILE* f;
	f = fopen("les_miserables_preface.txt", "r");
	
	if(f == NULL){
		return 1;
	}
	const char* delim = " .,;-:0123456789?!\"*+()|&[]#$/%%' \n \t " ""; 
	unsigned char hash[HASH_LENGTH] = {0};
	
	
	//Dies ist die Aufgabenstellung
	/*
	 * - find all unique words from the book
	 * - create the hashes of all two-string combinations
	 * - try to speed it up
	 * Usage example (not complete!):
	 */ 
	  char* words[1000000]; //1 Million Wörter können gespeichert werden
	  char c;		//nächstes Zeichen einlesen
	  char buffer[1024]; //aktuelles Wort
	  int letterCount = 0; //Anzahl der Buchstaben im aktuellen Wort
	  int wordCount = 0; //Anzahl der Wörter
	 
	  while ((c = fgetc(f)) != EOF) {
	      char needle[2] = {c};
	    if (!strstr(delim, needle)) { //es dürfen keine Steuerzeichen etc. eingelesen werden
		buffer[letterCount++] = c;
	    } else {
		buffer[letterCount++] = '\0';
		if (letterCount > 1) {
			char* tmp;
			if ((tmp = malloc(letterCount * sizeof(char))) == NULL) return -1;
			strncpy(tmp, buffer, letterCount); //aktuelles Wort an Adresse von Pointer tmp kopieren
			
			int i = 0;
			int match = 0;
			#pragma omp parallel private(i)
			while(i < wordCount) {
			    if(strcmp(tmp, words[i]) == 0) { //prüft, ob das aktuelle Wort bereits eingelesen wurde
				match = 1;
				i = wordCount;
			    }
			    else  i++;
			}
			if(match == 0) { 
			    words[wordCount] = tmp; //eingelesenes Wort wird gespeichert
			    wordCount++;
			}
			
		}
		letterCount = 0; 
	    }
	  }
	  //nach String-Kombination mit Hilfe von MD5 suchen
		MD5_CTX md5_ctx;
		int i,j;
		int shedule = wordCount; //Arbeitseinheiten werden in Größe shedule an einzelne Threads zugewiesen
		#pragma omp parallel for private(i) schedule(dynamic, shedule)
		for(i=0;i<wordCount;i++) {
		  #pragma omp parallel for shared(words) private(j) schedule(dynamic, shedule)
		  for(j=0;j<wordCount;j++) {
			#pragma omp task
			MD5_Init(&md5_ctx);
			#pragma omp task
			MD5_Update(&md5_ctx, words[i], strlen(words[i]));
			#pragma omp task
			MD5_Update(&md5_ctx," ", strlen(" "));
			#pragma omp task
			MD5_Update(&md5_ctx, words[j], strlen(words[j]));
			#pragma omp task
			MD5_Final(hash, &md5_ctx);
			if (memcmp(hash, target, HASH_LENGTH) == 0) { //wenn alle Bytes von hash, denen von target entspricht, ist das Wort gefunden
			     printf("%s %s\n", words[i], words[j]);
			     printf("\n");
			     int k;
			     #pragma omp parallel for private(k)
			     for(k=0;k<HASH_LENGTH;k++) {
				  printf("%x",hash[k]); //zugehörigen hash ausgeben
			     }
			     printf("\n"); 
			}
		  } 
		}
		
//Der Rest des Codes war vorgegeben
	time_t end = time(NULL);
	printf("Execution took ~%fs\n", difftime(end, start));
	return 0;
}
Auf diesen Beitrag antworten »
Karlito

Hi,

Sorry für die späte Meldung.

Du solltest einen Teil des Hashes (Präfix, Suffix oder Modul) als index für das Array verwenden, in dem Du die Wörter speicherst. Somit musst Du nicht jedes mal alle Wörter in der bestehenden Liste vergleichen, sondern musst nur in dem entsprechenden Eintrag schauen, ob der Hash nur zufällig gleich ist.

Um dann nach gleichen Hashes zu schauen, müsstest Du nur das gesamte Array durchgehen und in Einträgen mit zwei oder mehr Wörtern schauen, ob der Hash wirklich gleich ist.

Somit müsstest Du auch im Nachhinein nicht alle Wörter mit allen vergleichen, da Du die potentiellen Gleichen Hashes ja schon ermittelt hast. Der Aufwand würde sich so stark minimieren (gegenüber der aktuellen Implementierung).

Gruß,

Karlito
Auf diesen Beitrag antworten »
Karlito

Hier der Quelltext (etwas chaoitisch) von einem XML-Parser, den ich mal geschrieben habe um eine Liste aller in Wikipedia vorkommenden Wörter zu erstellen. Der Dump ist ca 12 GB groß und die Indizierung läuft in unter 10 Min. Der Hash (FNV) ist nicht 100%ig optimal. Man kann den Hash auf eine bestimmte Bit-Länge optimieren, was ich hier nicht gemacht hatte.

Es ist quasi eine Hash-Tabelle, welche keine flexible Größe hat. Dabei wird das Modul des FNV-Hashes verwendet, um ein Bucket zu adressieren. In einem Bucket befinden sich dann Einträge (LinkedList von Entries) mit dem selben Hashmodul.

Um einen Hash oder Wort zu Suchen muss man nur noch das Modul des Hashes als Adresse für das Bucket verwenden und bekommt die entsprechenden Einträge.

Ich habe hier außerdem den Stringvergleich selbst implementiert, weil strncmp eine Edit-Distanz liefert. Dazu muss mehr Arbeit getan werden, als einfach nur nach dem ersten Unterschied zu suchen und sollte damit schneller sein. Alternativen habe ich mir noch nicht angeschaut...

Gruß,

Karlito

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
278:
279:
280:
281:
282:
283:
284:
285:
286:
287:
288:
289:
290:
291:
292:
293:
294:
295:
296:
297:
298:
299:
300:
301:
302:
303:
304:
305:
306:
307:
308:
309:
310:
311:
312:
313:
314:
315:
316:
317:
318:
319:
320:
321:
322:
323:
324:
325:
326:
327:
328:
329:
330:
331:
332:
333:
334:
335:
#include <stdio.h>
#include <string.h>
#include <wchar.h>
#include <stdint.h>
#include <ctype.h>
#include <libxml/tree.h>
#include <libxml/xmlreader.h>
#include <libxml/parser.h>
#include <libxml/parserInternals.h>

#define CONST_BUCKETS_COUNT (128*1024*1024)
#define CONST_INIT_WORDLIST_SIZE 1024
#define CONST_INIT_CONTENT_BUFFER_SIZE 1024

typedef struct _Entry Entry;
struct _Entry {
	uint64_t wordOffset;
	uint32_t count;
	Entry *next;
};

typedef struct _WordList WordList;
struct _WordList{
	char *words;
	size_t wordsLength;
	uint64_t wordsPos;
	Entry *buckets;
	int bucketsCount;
};

typedef struct _Content Content;
struct _Content {
	char *buffer;
	int len;
	size_t allocated_size;
};

typedef struct _parserState ParserState;
struct _parserState{
	int level;
	int state;
	Content content[1];
	WordList wordList[1];
};

uint64_t fnFNV(const char* word){
	uint64_t nHashVal    = 0xcbf29ce484222325ULL,
				   nMagicPrime = 0x00000100000001b3ULL;

	while(word[0]){
		nHashVal ^= *word++;
		nHashVal *= nMagicPrime;
	}

	return nHashVal;
}

void startDocumentHandler(ParserState *state){
	state->level = 0;
	state->state = 0;
	state->content->buffer = (char *)malloc(CONST_INIT_CONTENT_BUFFER_SIZE);
	state->content->len = 0;
	state->content->allocated_size = CONST_INIT_CONTENT_BUFFER_SIZE;
	state->wordList->words = (char *)malloc(sizeof(char)*CONST_INIT_WORDLIST_SIZE);
	state->wordList->wordsLength = sizeof(char)*CONST_INIT_WORDLIST_SIZE;
	state->wordList->wordsPos = 0;
	state->wordList->buckets = (Entry *)calloc(CONST_BUCKETS_COUNT, sizeof(Entry));
	state->wordList->bucketsCount = CONST_BUCKETS_COUNT;
};

void print_wordlist(ParserState *state){
	int i, cnt=0;
	Entry *bucket;
	for(i=0;i<CONST_BUCKETS_COUNT;i++){
		if(state->wordList->buckets[i].wordOffset != 0){
			cnt++;
			printf("%s\n", &state->wordList->words[state->wordList->buckets[i].wordOffset]);
			bucket = state->wordList->buckets[i].next;
			while(bucket){
				printf("%s\n", &state->wordList->words[bucket->wordOffset]);
				bucket = bucket->next;
				cnt++;
			}
		}
	}
	printf("%d\n", cnt);
}

void print_stats(ParserState *state){
	int i, used_bucket_count = 0, collissions_count = 0;
	Entry *bucket;
	uint32_t max = 1;
	uint32_t *occurances;
	uint32_t *tmp;
	occurances = (uint32_t *)calloc(sizeof(uint32_t),max);
	for(i=0;i<CONST_BUCKETS_COUNT;i++){
		if(state->wordList->buckets[i].wordOffset != 0){
			bucket = &state->wordList->buckets[i];
			used_bucket_count++;
			if(max<bucket->count){
				tmp = (uint32_t *)calloc(sizeof(uint32_t),bucket->count);
				memcpy(tmp, occurances, sizeof(uint32_t)*max);
				max=bucket->count;
				free(occurances);
				occurances = tmp;
				printf("%9d, %s\n", max, &state->wordList->words[bucket->wordOffset]);
			}
			occurances[bucket->count - 1]++;
			bucket = state->wordList->buckets[i].next;
			while(bucket){
				if(max<bucket->count){
					tmp = (uint32_t *)calloc(sizeof(uint32_t),bucket->count);
					memcpy(tmp, occurances, sizeof(uint32_t)*max);
					max=bucket->count;
					free(occurances);
					occurances = tmp;
					printf("%9d, %s\n", max, &state->wordList->words[bucket->wordOffset]);
				}
				occurances[bucket->count - 1]++;
				bucket = bucket->next;
				collissions_count++;
			}
		}
	}
	printf("Stats:\n");
	printf("%15s %15s %15s %15s\n", "buckets avail", "buckets used", "colls ct", "words ct");
	printf("%15d %15d %15d %15d\n", CONST_BUCKETS_COUNT, used_bucket_count, collissions_count, used_bucket_count + collissions_count);
	printf("\n");
	for(i=0;i<max;i++){
		if(occurances[i]){
			printf("%9d %d\n", i+1, occurances[i]);
		}
	}
}

void free_buckets(Entry *bucket){
	if(bucket->next){
		free_buckets(bucket->next);
	}
	free(bucket);
}

void save_wordlist(WordList *wordList){
	FILE *fptr;
	int i;
	Entry *bucket;

	fptr = fopen("wordList.bin", "w");
	if(!fptr){
		printf("the wordlist-file could not be opened.\n");
	} else {
		for(i=0;i<CONST_BUCKETS_COUNT;i++){
			if(wordList->buckets[i].wordOffset){
				bucket = &wordList->buckets[i];
				if(bucket->count>100){
					fprintf(fptr, "%s%c", &wordList->words[bucket->wordOffset], '\0');
				}
			}
		}

		//fwrite(wordList->words, 1, wordList->wordsPos, fptr);

		fclose(fptr);
	}
}

void endDocumentHandler(ParserState *state){
	int i;
	//print_wordlist(state);
  print_stats(state);
	save_wordlist(state->wordList);
	state->level = 0;
	state->state = 0;
	free(state->content->buffer);
	free(state->wordList->words);
	for(i=0;i<CONST_BUCKETS_COUNT;i++){
		if(state->wordList->buckets[i].next){
			free_buckets(state->wordList->buckets[i].next);
		}
	}
	free(state->wordList->buckets);
}

void appendContent(ParserState *state, const xmlChar *buffer, int len){
	while(state->content->allocated_size<state->content->len+len+1){
		state->content->allocated_size*=2;
		state->content->buffer = (char *)realloc(state->content->buffer, state->content->allocated_size);
	}

	memcpy(&state->content->buffer[state->content->len], buffer, len);
	state->content->len+=len;
	state->content->buffer[state->content->len] = 0;
}

void appendWordList(WordList *wordList, char *word){
	int len;
	len = strlen(word);
	while(wordList->wordsPos+len+1>=wordList->wordsLength-1){
		printf("resize: %lu, %lu\n", wordList->wordsLength*2, wordList->wordsPos);
		wordList->words = (char *)realloc(wordList->words, wordList->wordsLength*2);
		wordList->wordsLength*=2;
	}
	memcpy(&wordList->words[wordList->wordsPos], word, len);
	wordList->words[wordList->wordsPos+len] = '\0';
	wordList->wordsPos+=len+1;
}

int cmpStrings(char *a, char *b){
	while(a[0]&&b[0]){
		if(a[0]!=b[0]) return 0;
		a++;
		b++;
	}
	return (a[0]==b[0]);
}

void insertUniqe(ParserState *state, char *word){
	uint64_t hash;
	Entry *bucket;
	WordList *wordList;
	
	hash = fnFNV(word)%CONST_BUCKETS_COUNT;
	bucket = &state->wordList->buckets[hash];
	wordList = state->wordList;
	if(bucket->wordOffset == 0){
		bucket->wordOffset = wordList->wordsPos;
		bucket->count = 1;
	} else {
		if(cmpStrings(&wordList->words[bucket->wordOffset], word)) { bucket->count +=1; return;}
		while(bucket->next){
			bucket = bucket->next;
			if(cmpStrings(&wordList->words[bucket->wordOffset], word)) { bucket->count +=1; return;}
		}
		bucket->next = (Entry *)calloc(1, sizeof(Entry));
		bucket = bucket->next;
		bucket->wordOffset = wordList->wordsPos;
		bucket->count = 1;
	}
	appendWordList(state->wordList, word);
}

void to_lower(char *word){
	while(word[0]){
		word[0] = tolower(word[0]);
		word++;
	}
}

void createWordList(ParserState *state, char *text){
	char *pch;
	char *split = " \"\\/\n\t,-_'<>|().:;=[]{}";
	pch = strtok(text, split);
	while(pch!=NULL){
		//to_lower(pch);
		insertUniqe(state, pch);
		pch = strtok(NULL, split);
	}
}

void startElementHandler(ParserState *state, char *name, char **atts){
	if(!strcmp("text", name)){
		state->state=2;
	}
	if(!strcmp("title", name)){
		state->state=1;
	}
	state->level++;
}

void endElementHandler(ParserState *state, char *name, char **atts){
	static int narf = 0;
	state->level--;
	if(state->state==2){
		narf++;
		createWordList(state, state->content->buffer);
		if(!(narf%1000)) printf("narf: %d\n", narf);
	}
	state->content->len=0;
	state->state=0;
}

void characterHandler(ParserState *state, const xmlChar *content, int len){
	if(state->state==2){
		appendContent(state, content, len);
	}
}

static xmlSAXHandler SAXParser = {
    0, /* internalSubset */
    0, /* isStandalone */
    0, /* hasInternalSubset */
    0, /* hasExternalSubset */
    0, /* resolveEntity */
    0, /* getEntity */
    0, /* entityDecl */
    0, /* notationDecl */
    0, /* attributeDecl */
    0, /* elementDecl */
    0, /* unparsedEntityDecl */
    0, /* setDocumentLocator */
    (startDocumentSAXFunc)startDocumentHandler, /* startDocument */
    (endDocumentSAXFunc)endDocumentHandler, /* endDocument */
    (startElementSAXFunc)startElementHandler, /* startElement */
    (endElementSAXFunc)endElementHandler, /* endElement */
    0, /* reference */
    (charactersSAXFunc)characterHandler, /* characters */
    0, /* ignorableWhitespace */
    0, /* processingInstruction */
    0, /* comment */
    0, /* warning */
    0, /* error */
    0, /* fatalError */
};

int main(int argc, char **argv){
	ParserState state;
	xmlParserCtxtPtr ctxt;

	if(argc==2){
		ctxt = xmlCreateFileParserCtxt(argv[1]);

		if(!ctxt) return EXIT_FAILURE;

		ctxt->sax = &SAXParser;
		ctxt->userData = &state;

		xmlParseDocument(ctxt);
				

	} else {
		printf("Fehler!\n");
	}
}
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »