{"thread":{"id":"4566","subject":"Re: Broken PPC sha1.. (Re: Figured out how to get Mozilla into git)","startedAt":"2006-06-19T08:41:35Z","lastAt":"2006-06-27T22:50:03Z","messageCount":5,"participants":["linux@horizon.com","Johannes Schindelin","Benjamin Herrenschmidt"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"22058","messageId":"20060619084135.18632.qmail@science.horizon.com","threadId":"4566","inReplyTo":null,"subject":"Re: Broken PPC sha1.. (Re: Figured out how to get Mozilla into git)","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2006-06-19T08:41:35Z","receivedAt":"2006-06-19T08:41:35Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"By the way, if anyone's still interested, I tried to produce a\nbetter-scheduled PowerPC sha1 core last year. Unfortunately, I don't have\naccess to a PowerPC machine to test on, so debugging is a little painful.\n\nThe latest version is appended, if anyone with a PowerPC machine wants to\ntry it out. It should drop in for ppc/sha1ppc.S. Hopefully the comments\nexplain the general idea.\n\nNotes I should add to the comments:\n- When reading the assembly code, note that PPC assembly permits a bare\n number (no %r prefix) as a register number, and further that number can\n be an expression! It makes the register renaming nice and simple.\n\n- Also for folks unfamiliar, it's dest,src,src operand order.\n\n- For a reminder, the PowerPC calling convention is:\n %r0 - Temp. Always reads as zero in some contexts.\n %r1 - stack pointer\n %r2 - Confusing. Different documents say different things.\n %r3..%r10 - Incoming arguments. Volatile across function calls.\n %r11..%r12 - Have some special uses not relevant here. Volatile.\n %r13..%r31 - Callee-save registers.\n %lr, %ctr - Volatile. %lr holds return address on input.\n\n And the way registers are used in this function are:\n %r0 - Temp.\n %r1 - Stack pointer. Used only for register saving.\n %r2 - Not used.\n %r3 - Points to hash accumulator A..E in memory.\n %r4 - Points to data being hashed.\n %r5 - Incoming loop count. Holds round constant K in body of loop.\n %r6..%r10 - Working copies of A..E\n %r11..%r26 - The W[] array of 16 input words being hashed\n %r27..%r31 - Start-of-round copies of A..E.\n %ctr - Holds loop count, copied from incoming %r5\n %lr - Holds return address. Not modified.\n\n- While I try to use the load/store multiple instructions where\n appropriate, they have a severe penalty for unaligned operands\n (they're microcoded optimistically, so do a full failing aligned\n load before being re-issued as a slow-but-safe unaligned sequence),\n and thanks to git's object type prefix, the source data is generally\n unaligned, so they're deliberately NOT used to load the 16 words of\n data hashed each iteration.\n\n/*\n * SHA-1 implementation for PowerPC.\n *\n * Copyright (C) 2005 Paul Mackerras \n */\n\n/*\n * We roll the registers for A, B, C, D, E around on each\n * iteration; E on iteration t is D on iteration t+1, and so on.\n * We use registers 6 - 10 for this. (Registers 27 - 31 hold\n * the previous values.)\n */\n#define RA(t)\t(((t)+4)%5+6)\n#define RB(t)\t(((t)+3)%5+6)\n#define RC(t)\t(((t)+2)%5+6)\n#define RD(t)\t(((t)+1)%5+6)\n#define RE(t)\t(((t)+0)%5+6)\n\n/* We use registers 11 - 26 for the W values */\n#define W(t)\t((t)%16+11)\n\n/* Register 5 is used for the constant k */\n\n/*\n * There are three F functions, used four groups of 20:\n * - 20 rounds of f0(b,c,d) = \"bit wise b ? c : d\" = (^b & d) + (b & c)\n * - 20 rounds of f1(b,c,d) = b^c^d = (b^d)^c\n * - 20 rounds of f2(b,c,d) = majority(b,c,d) = (b&d) + ((b^d)&c)\n * - 20 more rounds of f1(b,c,d)\n *\n * These are all scheduled for near-optimal performance on a G4.\n * The G4 is a 3-issue out-of-order machine with 3 ALUs, but it can only\n * *consider* starting the oldest 3 instructions per cycle. So to get\n * maximum performace out of it, you have to treat it as an in-order\n * machine. Which means interleaving the computation round t with the\n * computation of W[t+4].\n *\n * The first 16 rounds use W values loaded directly from memory, while the\n * remianing 64 use values computed from those first 16. We preload\n * 4 values before starting, so there are three kinds of rounds:\n * - The first 12 (all f0) also load the W values from memory.\n * - The next 64 compute W(i+4) in parallel. 8*f0, 20*f1, 20*f2, 16*f1.\n * - The last 4 (all f1) do not do anything with W.\n *\n * Therefore, we have 6 different round functions:\n * STEPD0_LOAD(t,s) - Perform round t and load W(s). s < 16\n * STEPD0_UPDATE(t,s) - Perform round t and compute W(s). s >= 16.\n * STEPD1_UPDATE(t,s)\n * STEPD2_UPDATE(t,s)\n * STEPD1(t) - Perform round t with no load or update.\n * \n * The G5 is more fully out-of-order, and can find the parallelism\n * by itself. The big limit is that it has a 2-cycle ALU latency, so\n * even though it's 2-way, the code has to be scheduled as if it's\n * 4-way, which can be a limit. To help it, we try to schedule the\n * read of RA(t) as late as possible so it doesn't stall waiting for\n * the previous round's RE(t-1), and we try to rotate RB(t) as early\n * as possible while reading RC(t) (= RB(t-1)) as late as possible.\n */\n\n\n/* the initial loads. */\n#define LOADW(s) \\\n\tlwz\tW(s),(s)*4(%r4)\n\n/*\n * This is actually 13 instructions, which is an awkward fit,\n * and uses W(s) as a temporary before loading it.\n */\n#define STEPD0_LOAD(t,s) \\\nadd RE(t),RE(t),W(t); andc %r0,RD(t),RB(t); /* spare slot */ \\\nadd RE(t),RE(t),%r0; and W(s),RC(t),RB(t); rotlwi %r0,RA(t),5; \\\nadd RE(t),RE(t),W(s); add %r0,%r0,%r5; rotlwi RB(t),RB(t),30; \\\nadd RE(t),RE(t),%r0; lwz W(s),(s)*4(%r4);\n\n/*\n * This can execute starting with 2 out of 3 possible moduli, so it\n * does 2 rounds in 9 cycles, 4.5 cycles/round.\n */\n#define STEPD0_UPDATE(t,s) \\\nadd RE(t),RE(t),W(t); andc %r0,RD(t),RB(t); xor W(s),W((s)-16),W((s)-3); \\\nadd RE(t),RE(t),%r0; and %r0,RC(t),RB(t); xor W(s),W(s),W((s)-8); \\\nadd RE(t),RE(t),%r0; rotlwi %r0,RA(t),5; xor W(s),W(s),W((s)-14); \\\nadd RE(t),RE(t),%r5; rotlwi RB(t),RB(t),30; rotlwi W(s),W(s),1; \\\nadd RE(t),RE(t),%r0;\n\n/* Nicely optimal. Conveniently, also the most common. */\n#define STEPD1_UPDATE(t,s) \\\nadd RE(t),RE(t),W(t); xor %r0,RD(t),RB(t); xor W(s),W((s)-16),W((s)-3); \\\nadd RE(t),RE(t),%r5; xor %r0,%r0,RC(t); xor W(s),W(s),W((s)-8); \\\nadd RE(t),RE(t),%r0; rotlwi %r0,RA(t),5; xor W(s),W(s),W((s)-14); \\\nadd RE(t),RE(t),%r0; rotlwi RB(t),RB(t),30; rotlwi W(s),W(s),1;\n\n/*\n * The naked version, no UPDATE, for the last 4 rounds. 3 cycles per.\n * We could use W(s) as a temp register, but we don't need it.\n */\n#define STEPD1(t) \\\n/* spare slot */ add RE(t),RE(t),W(t); xor %r0,RD(t),RB(t); \\\nrotlwi RB(t),RB(t),30; add RE(t),RE(t),%r5; xor %r0,%r0,RC(t); \\\nadd RE(t),RE(t),%r0; rotlwi %r0,RA(t),5; /* idle */ \\\nadd RE(t),RE(t),%r0;\n\n/* 5 cycles per */\n#define STEPD2_UPDATE(t,s) \\\nadd RE(t),RE(t),W(t); and %r0,RD(t),RB(t); xor W(s),W((s)-16),W((s)-3); \\\nadd RE(t),RE(t),%r0; xor %r0,RD(t),RB(t); xor W(s),W(s),W((s)-8); \\\nadd RE(t),RE(t),%r5; and %r0,%r0,RC(t); xor W(s),W(s),W((s)-14); \\\nadd RE(t),RE(t),%r0; rotlwi %r0,RA(t),5; rotlwi W(s),W(s),1; \\\nadd RE(t),RE(t),%r0; rotlwi RB(t),RB(t),30;\n\n#define STEP0_LOAD4(t,s)\t\t\\\n\tSTEPD0_LOAD(t,s);\t\t\\\n\tSTEPD0_LOAD((t+1),(s)+1);\t\\\n\tSTEPD0_LOAD((t)+2,(s)+2);\t\\\n\tSTEPD0_LOAD((t)+3,(s)+3);\n\n#define STEPUP4(fn, t, s)\t\t\\\n\tSTEP##fn##_UPDATE(t,s);\t\t\\\n\tSTEP##fn##_UPDATE((t)+1,(s)+1);\t\\\n\tSTEP##fn##_UPDATE((t)+2,(s)+2);\t\\\n\tSTEP##fn##_UPDATE((t)+3,(s)+3);\t\\\n\n#define STEPUP20(fn, t, s)\t\t\\\n\tSTEPUP4(fn, t, s);\t\t\\\n\tSTEPUP4(fn, (t)+4, (s)+4);\t\\\n\tSTEPUP4(fn, (t)+8, (s)+8);\t\\\n\tSTEPUP4(fn, (t)+12, (s)+12);\t\\\n\tSTEPUP4(fn, (t)+16, (s)+16)\n\n\t.globl\tsha1_core\nsha1_core:\n\tstwu\t%r1,-80(%r1)\n\tstmw\t%r13,4(%r1)\n\n\t/* Load up A - E */\n\tlmw\t%r27,0(%r3)\n\n\tmtctr\t%r5\n\n1:\n\tlis\t%r5,0x5a82\t/* K0-19 */\n\tmr\tRA(0),%r27\n\tLOADW(0)\n\tmr\tRB(0),%r28\n\tLOADW(1)\n\tmr\tRC(0),%r29\n\tLOADW(2)\n\tori\t%r5,%r5,0x7999\n\tmr\tRD(0),%r30\n\tLOADW(3)\n\tmr\tRE(0),%r31\n\n\tSTEP0_LOAD4(0, 4)\n\tSTEP0_LOAD4(4, 8)\n\tSTEP0_LOAD4(8, 12)\n\tSTEPUP4(D0, 12, 16)\n\tSTEPUP4(D0, 16, 20)\n\n\tlis\t%r5,0x6ed9\t/* K20-39 */\n\tori\t%r5,%r5,0xeba1\n\tSTEPUP20(D1, 20, 24)\n\n\tlis\t%r5,0x8f1b\t/* K40-59 */\n\tori\t%r5,%r5,0xbcdc\n\tSTEPUP20(D2, 40, 44)\n\n\tlis\t%r5,0xca62\t/* K60-79 */\n\tori\t%r5,%r5,0xc1d6\n\tSTEPUP4(D1, 60, 64)\n\tSTEPUP4(D1, 64, 68)\n\tSTEPUP4(D1, 68, 72)\n\tSTEPUP4(D1, 72, 76)\n\tSTEPD1(76)\n\tSTEPD1(77)\n\tSTEPD1(78)\n\tSTEPD1(79)\n\n\t/* Add results to original values */\n\tadd\t%r31,%r31,RE(0)\n\tadd\t%r30,%r30,RD(0)\n\tadd\t%r29,%r29,RC(0)\n\tadd\t%r28,%r28,RB(0)\n\tadd\t%r27,%r27,RA(0)\n\n\taddi\t%r4,%r4,64\n\tbdnz\t1b\n\n\t/* Save final hash, restore registers, and return */\n\tstmw\t%r27,0(%r3)\n\tlmw\t%r13,4(%r1)\n\taddi\t%r1,%r1,80\n\tblr\n"},{"id":"22059","messageId":"Pine.LNX.4.63.0606191049010.26329@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"4566","inReplyTo":"20060619084135.18632.qmail@science.horizon.com","subject":"Re: Broken PPC sha1.. (Re: Figured out how to get Mozilla into git)","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-06-19T08:50:24Z","receivedAt":"2006-06-19T08:50:24Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 19 Jun 2006, linux@horizon.com wrote:\n\n> By the way, if anyone's still interested, I tried to produce a\n> better-scheduled PowerPC sha1 core last year. Unfortunately, I don't have\n> access to a PowerPC machine to test on, so debugging is a little painful.\n\nIf you have access to SourceForge's compile farm, they have a PPC-G5 \nthere.\n\nCiao,\nDscho\n"},{"id":"22330","messageId":"20060623000908.9370.qmail@science.horizon.com","threadId":"4566","inReplyTo":"20060619084135.18632.qmail@science.horizon.com","subject":"Fixed PPC SHA1","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2006-06-23T00:09:08Z","receivedAt":"2006-06-23T00:09:08Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"Okay, here's a tested and working version (the earlier version worked,\ntoo) of a better-scheduled PPC SHA1. This is about 15% faster that the\ncurrent sha1ppc.S on a G4, and 5% faster on a G5 when hashing 10 million\nbytes, unaligned. (The G5 ratio seems to get better as the sizes fall.)\n\nIt's also somewhat smaller, due to using load-multiple instructions.\n\nI have a variant that uses load string (lswi) to load the values to be\nhashed that is a few percent faster on a G5, but a few percent slower\non a G4. It's also 52 bytes smaller (out of 4000).\n\nDoes anyone have any feeling for the ratio of G4 and G5 machines\nout there? I presume for that small a percentage, run-time processor\ndetection isn't worth it. (Cc: to linuxppc-dev for the experts on\nthis question.)\n\nI've tried using lmw to load the data, and it's faster if the data is\naligned, but it absolutely dies if the data is not. And due to git's\nvariable-sized hash prefix, most of git's hashes are of unaligned data.\n\n(No copyright is claimed on the changes to Paul Mackerras' work below.\nEnjoy.)\n\n/*\n * SHA-1 implementation for PowerPC.\n *\n * Copyright (C) 2005 Paul Mackerras \n */\n\n/*\n * PowerPC calling convention:\n * %r0 - volatile temp\n * %r1 - stack pointer.\n * %r2 - reserved\n * %r3-%r12 - Incoming arguments & return values; volatile.\n * %r13-%r31 - Callee-save registers\n * %lr - Return address, volatile\n * %ctr - volatile\n *\n * Register usage in this routine:\n * %r0 - temp\n * %r3 - argument (pointer to 5 words of SHA state)\n * %r4 - argument (pointer to data to hash)\n * %r5 - Contant K in SHA round (initially number of blocks to hash)\n * %r6-%r10 - Working copies of SHA variables A..E (actually E..A order)\n * %r11-%r26 - Data being hashed W[].\n * %r27-%r31 - Previous copies of A..E, for final add back.\n * %ctr - loop count\n */\n\n\n/*\n * We roll the registers for A, B, C, D, E around on each\n * iteration; E on iteration t is D on iteration t+1, and so on.\n * We use registers 6 - 10 for this. (Registers 27 - 31 hold\n * the previous values.)\n */\n#define RA(t)\t(((t)+4)%5+6)\n#define RB(t)\t(((t)+3)%5+6)\n#define RC(t)\t(((t)+2)%5+6)\n#define RD(t)\t(((t)+1)%5+6)\n#define RE(t)\t(((t)+0)%5+6)\n\n/* We use registers 11 - 26 for the W values */\n#define W(t)\t((t)%16+11)\n\n/* Register 5 is used for the constant k */\n\n/*\n * The basic SHA-1 round function is:\n * E += ROTL(A,5) + F(B,C,D) + W[i] + K; B = ROTL(B,30)\n * Then the variables are renamed: (A,B,C,D,E) = (E,A,B,C,D).\n *\n * Every 20 rounds, the function F() and the contant K changes:\n * - 20 rounds of f0(b,c,d) = \"bit wise b ? c : d\" = (^b & d) + (b & c)\n * - 20 rounds of f1(b,c,d) = b^c^d = (b^d)^c\n * - 20 rounds of f2(b,c,d) = majority(b,c,d) = (b&d) + ((b^d)&c)\n * - 20 more rounds of f1(b,c,d)\n *\n * These are all scheduled for near-optimal performance on a G4.\n * The G4 is a 3-issue out-of-order machine with 3 ALUs, but it can only\n * *consider* starting the oldest 3 instructions per cycle. So to get\n * maximum performace out of it, you have to treat it as an in-order\n * machine. Which means interleaving the computation round t with the\n * computation of W[t+4].\n *\n * The first 16 rounds use W values loaded directly from memory, while the\n * remianing 64 use values computed from those first 16. We preload\n * 4 values before starting, so there are three kinds of rounds:\n * - The first 12 (all f0) also load the W values from memory.\n * - The next 64 compute W(i+4) in parallel. 8*f0, 20*f1, 20*f2, 16*f1.\n * - The last 4 (all f1) do not do anything with W.\n *\n * Therefore, we have 6 different round functions:\n * STEPD0_LOAD(t,s) - Perform round t and load W(s). s < 16\n * STEPD0_UPDATE(t,s) - Perform round t and compute W(s). s >= 16.\n * STEPD1_UPDATE(t,s)\n * STEPD2_UPDATE(t,s)\n * STEPD1(t) - Perform round t with no load or update.\n * \n * The G5 is more fully out-of-order, and can find the parallelism\n * by itself. The big limit is that it has a 2-cycle ALU latency, so\n * even though it's 2-way, the code has to be scheduled as if it's\n * 4-way, which can be a limit. To help it, we try to schedule the\n * read of RA(t) as late as possible so it doesn't stall waiting for\n * the previous round's RE(t-1), and we try to rotate RB(t) as early\n * as possible while reading RC(t) (= RB(t-1)) as late as possible.\n */\n\n/* the initial loads. */\n#define LOADW(s) \\\n\tlwz\tW(s),(s)*4(%r4)\n\n/*\n * Perform a step with F0, and load W(s). Uses W(s) as a temporary\n * before loading it.\n * This is actually 10 instructions, which is an awkward fit.\n * It can execute grouped as listed, or delayed one instruction.\n * (If delayed two instructions, there is a stall before the start of the\n * second line.) Thus, two iterations take 7 cycles, 3.5 cycles per round.\n */\n#define STEPD0_LOAD(t,s) \\\nadd RE(t),RE(t),W(t); andc %r0,RD(t),RB(t); and W(s),RC(t),RB(t); \\\nadd RE(t),RE(t),%r0; rotlwi %r0,RA(t),5; rotlwi RB(t),RB(t),30; \\\nadd RE(t),RE(t),W(s); add %r0,%r0,%r5; lwz W(s),(s)*4(%r4); \\\nadd RE(t),RE(t),%r0\n\n/*\n * This is likewise awkward, 13 instructions. However, it can also\n * execute starting with 2 out of 3 possible moduli, so it does 2 rounds\n * in 9 cycles, 4.5 cycles/round.\n */\n#define STEPD0_UPDATE(t,s,loadk...) \\\nadd RE(t),RE(t),W(t); andc %r0,RD(t),RB(t); xor W(s),W((s)-16),W((s)-3); \\\nadd RE(t),RE(t),%r0; and %r0,RC(t),RB(t); xor W(s),W(s),W((s)-8); \\\nadd RE(t),RE(t),%r0; rotlwi %r0,RA(t),5; xor W(s),W(s),W((s)-14); \\\nadd RE(t),RE(t),%r5; loadk; rotlwi RB(t),RB(t),30; rotlwi W(s),W(s),1; \\\nadd RE(t),RE(t),%r0\n\n/* Nicely optimal. Conveniently, also the most common. */\n#define STEPD1_UPDATE(t,s,loadk...) \\\nadd RE(t),RE(t),W(t); xor %r0,RD(t),RB(t); xor W(s),W((s)-16),W((s)-3); \\\nadd RE(t),RE(t),%r5; loadk; xor %r0,%r0,RC(t); xor W(s),W(s),W((s)-8); \\\nadd RE(t),RE(t),%r0; rotlwi %r0,RA(t),5; xor W(s),W(s),W((s)-14); \\\nadd RE(t),RE(t),%r0; rotlwi RB(t),RB(t),30; rotlwi W(s),W(s),1\n\n/*\n * The naked version, no UPDATE, for the last 4 rounds. 3 cycles per.\n * We could use W(s) as a temp register, but we don't need it.\n */\n#define STEPD1(t) \\\n add RE(t),RE(t),W(t); xor %r0,RD(t),RB(t); \\\nrotlwi RB(t),RB(t),30; add RE(t),RE(t),%r5; xor %r0,%r0,RC(t); \\\nadd RE(t),RE(t),%r0; rotlwi %r0,RA(t),5; /* spare slot */ \\\nadd RE(t),RE(t),%r0\n\n/*\n * 14 instructions, 5 cycles per. The majority function is a bit\n * awkward to compute. This can execute with a 1-instruction delay,\n * but it causes a 2-instruction delay, which triggers a stall.\n */\n#define STEPD2_UPDATE(t,s,loadk...) \\\nadd RE(t),RE(t),W(t); and %r0,RD(t),RB(t); xor W(s),W((s)-16),W((s)-3); \\\nadd RE(t),RE(t),%r0; xor %r0,RD(t),RB(t); xor W(s),W(s),W((s)-8); \\\nadd RE(t),RE(t),%r5; loadk; and %r0,%r0,RC(t); xor W(s),W(s),W((s)-14); \\\nadd RE(t),RE(t),%r0; rotlwi %r0,RA(t),5; rotlwi W(s),W(s),1; \\\nadd RE(t),RE(t),%r0; rotlwi RB(t),RB(t),30\n\n#define STEP0_LOAD4(t,s)\t\t\\\n\tSTEPD0_LOAD(t,s);\t\t\\\n\tSTEPD0_LOAD((t+1),(s)+1);\t\\\n\tSTEPD0_LOAD((t)+2,(s)+2);\t\\\n\tSTEPD0_LOAD((t)+3,(s)+3)\n\n#define STEPUP4(fn, t, s, loadk...)\t\t\\\n\tSTEP##fn##_UPDATE(t,s,);\t\t\\\n\tSTEP##fn##_UPDATE((t)+1,(s)+1,);\t\\\n\tSTEP##fn##_UPDATE((t)+2,(s)+2,);\t\\\n\tSTEP##fn##_UPDATE((t)+3,(s)+3,loadk)\n\n#define STEPUP20(fn, t, s, loadk...)\t\\\n\tSTEPUP4(fn, t, s,);\t\t\\\n\tSTEPUP4(fn, (t)+4, (s)+4,);\t\\\n\tSTEPUP4(fn, (t)+8, (s)+8,);\t\\\n\tSTEPUP4(fn, (t)+12, (s)+12,);\t\\\n\tSTEPUP4(fn, (t)+16, (s)+16, loadk)\n\n\t.globl\tsha1_core\nsha1_core:\n\tstwu\t%r1,-80(%r1)\n\tstmw\t%r13,4(%r1)\n\n\t/* Load up A - E */\n\tlmw\t%r27,0(%r3)\n\n\tmtctr\t%r5\n\n1:\n\tLOADW(0)\n\tlis\t%r5,0x5a82\n\tmr\tRE(0),%r31\n\tLOADW(1)\n\tmr\tRD(0),%r30\n\tmr\tRC(0),%r29\n\tLOADW(2)\n\tori\t%r5,%r5,0x7999\t/* K0-19 */\n\tmr\tRB(0),%r28\n\tLOADW(3)\n\tmr\tRA(0),%r27\n\n\tSTEP0_LOAD4(0, 4)\n\tSTEP0_LOAD4(4, 8)\n\tSTEP0_LOAD4(8, 12)\n\tSTEPUP4(D0, 12, 16,)\n\tSTEPUP4(D0, 16, 20, lis %r5,0x6ed9)\n\n\tori\t%r5,%r5,0xeba1\t/* K20-39 */\n\tSTEPUP20(D1, 20, 24, lis %r5,0x8f1b)\n\n\tori\t%r5,%r5,0xbcdc\t/* K40-59 */\n\tSTEPUP20(D2, 40, 44, lis %r5,0xca62)\n\n\tori\t%r5,%r5,0xc1d6\t/* K60-79 */\n\tSTEPUP4(D1, 60, 64,)\n\tSTEPUP4(D1, 64, 68,)\n\tSTEPUP4(D1, 68, 72,)\n\tSTEPUP4(D1, 72, 76,)\n\taddi\t%r4,%r4,64\n\tSTEPD1(76)\n\tSTEPD1(77)\n\tSTEPD1(78)\n\tSTEPD1(79)\n\n\t/* Add results to original values */\n\tadd\t%r31,%r31,RE(0)\n\tadd\t%r30,%r30,RD(0)\n\tadd\t%r29,%r29,RC(0)\n\tadd\t%r28,%r28,RB(0)\n\tadd\t%r27,%r27,RA(0)\n\n\tbdnz\t1b\n\n\t/* Save final hash, restore registers, and return */\n\tstmw\t%r27,0(%r3)\n\tlmw\t%r13,4(%r1)\n\taddi\t%r1,%r1,80\n\tblr\n"},{"id":"22331","messageId":"20060623005456.21460.qmail@science.horizon.com","threadId":"4566","inReplyTo":"20060623000908.9370.qmail@science.horizon.com","subject":"Re: Fixed PPC SHA1","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2006-06-23T00:54:56Z","receivedAt":"2006-06-23T00:54:56Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"Here's the lwsi-based version that's slightly faster on a G5, but slightly\nslower on a G4.\n\n/*\n * SHA-1 implementation for PowerPC.\n *\n * Copyright (C) 2005 Paul Mackerras \n */\n\n/*\n * PowerPC calling convention:\n * %r0 - volatile temp\n * %r1 - stack pointer.\n * %r2 - reserved\n * %r3-%r12 - Incoming arguments & return values; volatile.\n * %r13-%r31 - Callee-save registers\n * %lr - Return address, volatile\n * %ctr - volatile\n *\n * Register usage in this routine:\n * %r0 - temp\n * %r3 - argument (pointer to 5 words of SHA state)\n * %r4 - argument (pointer to data to hash)\n * %r5-%r20 - Data being hashed W[]. (%r5 is initially count of blocks)\n * %r21 - Contant K in SHA round\n * %r22-%r26 - Working copies of SHA variables A..E (actually E..A order) \n * %r27-%r31 - Previous copies of A..E, for final add back.\n * %ctr - loop count (copied from %r5 argument)\n *\n * It's also worth mentioning that PPC assembly accept a bare\n * number as a register specifier; the \"%r\" prefix is actually optional.\n * And that number cna be an expression! That simplifies the\n * loop unrolling significantly.\n */\n\n/*\n * We roll the registers for A, B, C, D, E around on each\n * iteration; E on iteration t is D on iteration t+1, and so on.\n * We use registers 22 - 26 for this. (Registers 27 - 31 hold\n * the previous values.)\n */\n#define RA(t)\t(((t)+4)%5+22)\n#define RB(t)\t(((t)+3)%5+22)\n#define RC(t)\t(((t)+2)%5+22)\n#define RD(t)\t(((t)+1)%5+22)\n#define RE(t)\t(((t)+0)%5+22)\n\n/* Register 21 is used for the constant k */\n\n/* We use registers 5 - 20 for the W values */\n#define W(t)\t((t)%16+5)\n\n/*\n * The basic SHA-1 round function is:\n * E += ROTL(A,5) + F(B,C,D) + W[i] + K; B = ROTL(B,30)\n * Then the variables are renamed: (A,B,C,D,E) = (E,A,B,C,D).\n *\n * Every 20 rounds, the function F() and the contant K changes:\n * - 20 rounds of f0(b,c,d) = \"bit wise b ? c : d\" = (^b & d) + (b & c)\n * - 20 rounds of f1(b,c,d) = b^c^d = (b^d)^c\n * - 20 rounds of f2(b,c,d) = majority(b,c,d) = (b&d) + ((b^d)&c)\n * - 20 more rounds of f1(b,c,d)\n *\n * These are all scheduled for near-optimal performance on a G4.\n * The G4 is a 3-issue out-of-order machine with 3 ALUs, but it can only\n * *consider* starting the oldest 3 instructions per cycle. So to get\n * maximum performace out of it, you have to treat it as an in-order\n * machine. Which means interleaving the computation round t with the\n * computation of W[t+4].\n *\n * The first 16 rounds use W values loaded directly from memory, while the\n * remianing 64 use values computed from those first 16. We preload\n * 4 values before starting, so there are three kinds of rounds:\n * - The first 12 (all f0) also load the W values from memory.\n * - The next 64 compute W(i+4) in parallel. 8*f0, 20*f1, 20*f2, 16*f1.\n * - The last 4 (all f1) do not do anything with W.\n *\n * Therefore, we have 5 different round functions:\n * STEPD0(t,s) - Perform round t\n * STEPD0_UPDATE(t,s) - Perform round t and compute W(s). s >= 16.\n * STEPD1_UPDATE(t,s)\n * STEPD2_UPDATE(t,s)\n * STEPD1(t) - Perform round t with no load or update.\n *\n * There's also provision for inserting an instruction to start loading\n * the new K value after it's last used in the given step.\n * \n * The G5 is more fully out-of-order, and can find the parallelism\n * by itself. The big limit is that it has a 2-cycle ALU latency, so\n * even though it's 2-way, the code has to be scheduled as if it's\n * 4-way, which can be a limit. To help it, we try to schedule the\n * read of RA(t) as late as possible so it doesn't stall waiting for\n * the previous round's RE(t-1), and we try to rotate RB(t) as early\n * as possible while reading RC(t) (= RB(t-1)) as late as possible.\n */\n\n/*\n * Okay, we need a naked version of STEPD0. It's 9 instructions.\n * Can that be done in 3 cycles, WITHOUT using W(s) as a temp?\n * NO. So we need W(s) as a temp. That can be arranged with some\n * clever scheduling.\n */\n#define STEPD0(t,s) \\\n/* spare slot */ add RE(t),RE(t),W(t); andc %r0,RD(t),RB(t); \\\nadd RE(t),RE(t),%r0; and W(s),RC(t),RB(t); rotlwi %r0,RA(t),5; \\\nadd RE(t),RE(t),W(s); add %r0,%r0,%r21; rotlwi RB(t),RB(t),30; \\\nadd RE(t),RE(t),%r0;\n\n/*\n * This can execute starting with 2 out of 3 possible moduli, so it\n * does 2 rounds in 9 cycles, 4.5 cycles/round.\n */\n#define STEPD0_UPDATE(t,s,loadk...) \\\nadd RE(t),RE(t),W(t); andc %r0,RD(t),RB(t); xor W(s),W((s)-16),W((s)-3); \\\nadd RE(t),RE(t),%r0; and %r0,RC(t),RB(t); xor W(s),W(s),W((s)-8); \\\nadd RE(t),RE(t),%r0; rotlwi %r0,RA(t),5; xor W(s),W(s),W((s)-14); \\\nadd RE(t),RE(t),%r21; loadk; rotlwi RB(t),RB(t),30; rotlwi W(s),W(s),1; \\\nadd RE(t),RE(t),%r0\n\n/* Nicely optimal. Conveniently, also the most common. */\n#define STEPD1_UPDATE(t,s,loadk...) \\\nadd RE(t),RE(t),W(t); xor %r0,RD(t),RB(t); xor W(s),W((s)-16),W((s)-3); \\\nadd RE(t),RE(t),%r21; loadk; xor %r0,%r0,RC(t); xor W(s),W(s),W((s)-8); \\\nadd RE(t),RE(t),%r0; rotlwi %r0,RA(t),5; xor W(s),W(s),W((s)-14); \\\nadd RE(t),RE(t),%r0; rotlwi RB(t),RB(t),30; rotlwi W(s),W(s),1\n\n/*\n * The naked version, no UPDATE, for the last 4 rounds. 3 cycles per.\n * We could use W(s) as a temp register, but we don't need it.\n */\n#define STEPD1(t) \\\n add RE(t),RE(t),W(t); xor %r0,RD(t),RB(t); \\\nadd RE(t),RE(t),%r21; xor %r0,%r0,RC(t); rotlwi RB(t),RB(t),30; \\\nadd RE(t),RE(t),%r0; rotlwi %r0,RA(t),5; /* spare slot */ \\\nadd RE(t),RE(t),%r0\n\n/* 5 cycles per */\n#define STEPD2_UPDATE(t,s,loadk...) \\\nadd RE(t),RE(t),W(t); and %r0,RD(t),RB(t); xor W(s),W((s)-16),W((s)-3); \\\nadd RE(t),RE(t),%r0; xor %r0,RD(t),RB(t); xor W(s),W(s),W((s)-8); \\\nadd RE(t),RE(t),%r21; loadk; and %r0,%r0,RC(t); xor W(s),W(s),W((s)-14); \\\nadd RE(t),RE(t),%r0; rotlwi %r0,RA(t),5; rotlwi W(s),W(s),1; \\\nadd RE(t),RE(t),%r0; rotlwi RB(t),RB(t),30\n\n#define STEP0_LOAD4(t,s)\t\t\\\n\tSTEPD0_LOAD(t,s);\t\t\\\n\tSTEPD0_LOAD((t+1),(s)+1);\t\\\n\tSTEPD0_LOAD((t)+2,(s)+2);\t\\\n\tSTEPD0_LOAD((t)+3,(s)+3);\n\n#define STEP0_4(t,s)\t\t\\\n\tSTEPD0(t,s);\t\t\\\n\tSTEPD0((t+1),(s)+1);\t\\\n\tSTEPD0((t)+2,(s)+2);\t\\\n\tSTEPD0((t)+3,(s)+3);\n\n#define STEP1_4(t)\t\t\\\n\tSTEPD1(t);\t\t\\\n\tSTEPD1((t+1));\t\t\\\n\tSTEPD1((t)+2);\t\t\\\n\tSTEPD1((t)+3);\n\n#define STEPUP4(fn, t, s, loadk...)\t\t\\\n\tSTEP##fn##_UPDATE(t,s,);\t\t\\\n\tSTEP##fn##_UPDATE((t)+1,(s)+1,);\t\\\n\tSTEP##fn##_UPDATE((t)+2,(s)+2,);\t\\\n\tSTEP##fn##_UPDATE((t)+3,(s)+3,loadk)\n\n#define STEPUP20(fn, t, s, loadk...)\t\\\n\tSTEPUP4(fn, t, s,);\t\t\\\n\tSTEPUP4(fn, (t)+4, (s)+4,);\t\\\n\tSTEPUP4(fn, (t)+8, (s)+8,);\t\\\n\tSTEPUP4(fn, (t)+12, (s)+12,);\t\\\n\tSTEPUP4(fn, (t)+16, (s)+16, loadk)\n\n\t.globl\tsha1_core\nsha1_core:\n\tstwu\t%r1,-80(%r1)\n\tstmw\t%r13,4(%r1)\n\n\t/* Load up A - E */\n\tlmw\t%r27,0(%r3)\n\n\tmtctr\t%r5\n\n1:\n\tlswi\tW(0),%r4,32\n\tlis\t%r21,0x5a82\n\taddi\t%r4,%r4,32\n\tmr\tRE(0),%r31\n\tmr\tRD(0),%r30\n\tmr\tRC(0),%r29\n\tori\t%r21,%r21,0x7999\t/* K0-19 */\n\tmr\tRB(0),%r28\n\tmr\tRA(0),%r27\n\n\tSTEP0_4(0, 8)\n\tSTEP0_4(4, 12)\n\tlswi\tW(8),%r4,32\n\tSTEPUP4(D0, 8, 16,)\n\tSTEPUP4(D0, 12, 20,)\n\tSTEPUP4(D0, 16, 24, lis %r21,0x6ed9)\n\n\tori\t%r21,%r21,0xeba1\t/* K20-39 */\n\tSTEPUP20(D1, 20, 28, lis %r21,0x8f1b)\n\n\tori\t%r21,%r21,0xbcdc\t/* K40-59 */\n\tSTEPUP20(D2, 40, 48, lis %r21,0xca62)\n\n\tori\t%r21,%r21,0xc1d6\t/* K60-79 */\n\tSTEPUP4(D1, 60, 68,)\n\tSTEPUP4(D1, 64, 72,)\n\tSTEPUP4(D1, 68, 76,)\n\taddi\t%r4,%r4,32\n\tSTEP1_4(72);\n\tSTEP1_4(76);\n\n\t/* Add results to original values */\n\tadd\t%r31,%r31,RE(0)\n\tadd\t%r30,%r30,RD(0)\n\tadd\t%r29,%r29,RC(0)\n\tadd\t%r28,%r28,RB(0)\n\tadd\t%r27,%r27,RA(0)\n\n\tbdnz\t1b\n\n\t/* Save final hash, restore registers, and return */\n\tstmw\t%r27,0(%r3)\n\tlmw\t%r13,4(%r1)\n\taddi\t%r1,%r1,80\n\tblr\n"},{"id":"22693","messageId":"1151448603.2350.104.camel@localhost.localdomain","threadId":"4566","inReplyTo":"20060623005456.21460.qmail@science.horizon.com","subject":"Re: Fixed PPC SHA1","fromName":"Benjamin Herrenschmidt","fromEmail":"benh@kernel.crashing.org","sentAt":"2006-06-27T22:50:03Z","receivedAt":"2006-06-27T22:50:03Z","isPatch":false,"sender":{"key":"benh@kernel.crashing.org","avatar":null},"body":"On Thu, 2006-06-22 at 20:54 -0400, linux@horizon.com wrote:\n> Here's the lwsi-based version that's slightly faster on a G5, but slightly\n> slower on a G4.\n\nI wouldn't bother with 2 versions... use the non-string version (string\noperations will cause performance problems on other processors)\n\nBen.\n"}]}