Openwall GNU/*/Linux - a small security-enhanced Linux distro for servers
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Thu, 17 Sep 2015 07:27:30 +0300
From: Solar Designer <solar@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: Re: fast hash processing bottlenecks

On Wed, Sep 16, 2015 at 09:37:54PM +0200, magnum wrote:
> I think the rules engine has some low hanging fruit

The best64 rules use repeated simple commands, instead of using some of
our advanced commands.  The attached patch optimizes our handling of
that.  With it, the best64 rules run faster, whereas our more typical
rulesets continue to run at their usual speed.

The 29M testcase is now down to:

real    0m43.621s
user    2m56.879s
sys     0m17.599s

It might make sense to further optimize this by having repeated $ and ^
commands translated into A commands when the rules are first parsed,
like we do for no-op squeezing.

A possibly more important optimization I didn't bother with yet is
avoiding the copying from in to out in more commands, and instead moving
the start of string pointer by a few chars.  I didn't implement this so
far because it's potentially problematic: a large number of rule commands
would then be able to move the pointer to outside of its buffer.  We'd
need to check whether the pointer is still within bounds, and this would
partially defeat the performance gain from the lack of copying.
Alternatively, we could make the string buffers so much larger than the
rule buffer that this issue would be impossible.  (The start of string
pointers would need to be placed in the middle of the buffers initially.)

Alexander

diff -urp bleeding-jumbo-opt5/src/rules.c bleeding-jumbo-opt/src/rules.c
--- bleeding-jumbo-opt5/src/rules.c	2015-09-02 10:40:47 +0000
+++ bleeding-jumbo-opt/src/rules.c	2015-09-17 03:53:57 +0000
@@ -1539,18 +1539,46 @@ char *rules_apply(char *word_in, char *r
 
 		case '$':
 			VALUE(in[length++])
+			if (NEXT == '$') {
+				(void)RULE;
+				VALUE(in[length++])
+				if (NEXT == '$') {
+					(void)RULE;
+					VALUE(in[length++])
+				}
+			}
 			in[length] = 0;
 			break;
 
 		case '^':
 			{
-				char *out;
+				char *out, a, b;
 				GET_OUT
+				VALUE(a)
+				if (NEXT != '^') {
+					out[0] = a;
+					memcpy(&out[1], in, ++length);
+					in = out;
+					break;
+				}
+				(void)RULE;
+				VALUE(b)
+				if (NEXT != '^') {
+					out[0] = b;
+					out[1] = a;
+					memcpy(&out[2], in, length + 1);
+					length += 2;
+					in = out;
+					break;
+				}
+				(void)RULE;
 				VALUE(out[0])
-				strcpy(&out[1], in);
+				out[1] = b;
+				out[2] = a;
+				memcpy(&out[3], in, length + 1);
+				length += 3;
 				in = out;
 			}
-			length++;
 			break;
 
 		case 'x':
@@ -1641,20 +1669,34 @@ char *rules_apply(char *word_in, char *r
 
 /* Crack 5.0 rules */
 		case '[':
-			if (length) {
-				char *out;
-				GET_OUT
-				strcpy(out, &in[1]);
-				length--;
-				in = out;
-				break;
+			{
+				int count = 1;
+				while (NEXT == '[') {
+					(void)RULE;
+					count++;
+				}
+				if ((length -= count) > 0) {
+					char *out;
+					GET_OUT
+					memcpy(out, &in[count], length + 1);
+					in = out;
+					break;
+				}
+				in[length = 0] = 0;
 			}
-			in[0] = 0;
 			break;
 
 		case ']':
-			if (length)
-				in[--length] = 0;
+			{
+				int count = 1;
+				while (NEXT == ']') {
+					(void)RULE;
+					count++;
+				}
+				if ((length -= count) < 0)
+					length = 0;
+				in[length] = 0;
+			}
 			break;
 
 		case 'C':
@@ -1769,12 +1811,9 @@ char *rules_apply(char *word_in, char *r
 				int pos;
 				POSITION(pos)
 				if (pos < length) {
-					char *out;
-					GET_OUT
-					memcpy(out, in, pos);
-					strcpy(&out[pos], &in[pos + 1]);
+					memmove(&in[pos], &in[pos + 1],
+					    length - pos);
 					length--;
-					in = out;
 				}
 			}
 			break;
@@ -1782,10 +1821,19 @@ char *rules_apply(char *word_in, char *r
 		case '{':
 			if (length) {
 				char *out;
+				int count = 1;
+				while (NEXT == '{') {
+					(void)RULE;
+					count++;
+				}
+				while (count >= length)
+					count -= length;
+				if (!count)
+					break;
 				GET_OUT
-				strcpy(out, &in[1]);
-				in[1] = 0;
-				strcat(out, in);
+				memcpy(out, &in[count], length - count);
+				memcpy(&out[length - count], in, count);
+				out[length] = 0;
 				in = out;
 				break;
 			}
@@ -1796,10 +1844,19 @@ char *rules_apply(char *word_in, char *r
 			if (length) {
 				char *out;
 				int pos;
+				int count = 1;
+				while (NEXT == '}') {
+					(void)RULE;
+					count++;
+				}
+				while (count >= length)
+					count -= length;
+				if (!count)
+					break;
 				GET_OUT
-				out[0] = in[pos = length - 1];
-				in[pos] = 0;
-				strcpy(&out[1], in);
+				memcpy(out, &in[pos = length - count], count);
+				memcpy(&out[count], in, pos);
+				out[length] = 0;
 				in = out;
 				break;
 			}

Powered by blists - more mailing lists

Your e-mail address:

Powered by Openwall GNU/*/Linux - Powered by OpenVZ