source: icGREP/icgrep-devel/icgrep/kernels/lzparabix/LZParabixCompressionKernel.cpp @ 6114

Last change on this file since 6114 was 6114, checked in by xwa163, 13 months ago

Init check in for new compression format (lzparabix) related kernels and pipelines, including compressor, decoder and grep

File size: 21.2 KB
Line 
1
2#include "LZParabixCompressionKernel.h"
3
4#include <kernels/kernel_builder.h>
5#include <iostream>
6#include <string>
7#include <llvm/Support/raw_ostream.h>
8#include <kernels/streamset.h>
9#include <cstdint>
10
11
12#define HASHLOG (12)
13#define HASHNBCELLS4 (1 << HASHLOG)
14
15
16using namespace llvm;
17using namespace kernel;
18using namespace std;
19
20namespace kernel{
21
22
23
24
25    LZParabixCompressionKernel::LZParabixCompressionKernel(const std::unique_ptr<kernel::KernelBuilder> &b)
26    :SegmentOrientedKernel("LZParabixAioKernel",
27            // Inputs
28                           {
29                                   Binding{b->getStreamSetTy(1, 8), "byteStream", FixedRate()},
30                           },
31            //Outputs
32                           {
33                                   Binding{b->getStreamSetTy(1, 8), "outputStream", BoundedRate(0, 1)}
34                           },
35            //Arguments
36                           {
37                                   Binding{b->getSizeTy(), "fileSize"}
38                           },
39                           {},
40            //Internal states:
41                           {
42                                   // Two hashmap to optimize the performance of matching
43                                   Binding(ArrayType::get(b->getInt64Ty(), HASHNBCELLS4), "strToBlockIndex"),
44                                   Binding(ArrayType::get(b->getInt32Ty(), HASHNBCELLS4), "strToMatchPos")
45
46                           }),
47     mLzParabixBlockSize(4 * 1024 * 1024)
48    {
49        this->setStride(mLzParabixBlockSize);
50        addAttribute(MustExplicitlyTerminate());
51    }
52
53    void LZParabixCompressionKernel::generateDoSegmentMethod(const std::unique_ptr<KernelBuilder> &b) {
54        Value* inputCursor = b->getProcessedItemCount("byteStream");
55        Value* inputEndPos = b->CreateAdd(inputCursor, b->getSize(mLzParabixBlockSize));
56        Value* fileSize = b->getScalarField("fileSize");
57        inputEndPos = b->CreateUMin(inputEndPos, fileSize);
58        Value* outputCursor = b->getProducedItemCount("outputStream");
59//        b->CallPrintInt("inputCursor", inputCursor);
60        this->encodeBlock(b, inputCursor, inputEndPos, outputCursor);
61//        b->CallPrintInt("inputCursor:end", inputCursor);
62        b->setTerminationSignal(b->CreateICmpEQ(inputEndPos, fileSize));
63        b->setProcessedItemCount("byteStream", inputEndPos);
64    }
65
66    void LZParabixCompressionKernel::encodeBlock(const std::unique_ptr<KernelBuilder> &b, llvm::Value *inputCursor,
67                                                 llvm::Value *inputEndPos, llvm::Value *outputPos) {
68        // Constant
69        ConstantInt* SIZE_64 = b->getSize(64);
70
71        // ---- EntryBlock
72        BasicBlock* entryBlock = b->GetInsertBlock();
73
74        BasicBlock* encodeBlockCon = b->CreateBasicBlock("encodeBlockCon");
75        BasicBlock* encodeBlockBody = b->CreateBasicBlock("encodeBlockBody");
76        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
77
78        Value* blockSizePos = outputPos;
79
80        Value* initOutputCursor = b->CreateAdd(outputPos, b->getSize(4)); // blockSize takes 4 bytes
81        Value* initBlockIndex = b->CreateUDiv(inputCursor, b->getSize(64));
82
83
84        b->CreateBr(encodeBlockCon);
85
86        // ---- encodeBlockCon
87        b->SetInsertPoint(encodeBlockCon);
88
89        PHINode* phiInputCursorPos = b->CreatePHI(b->getSizeTy(), 3);
90        phiInputCursorPos->addIncoming(inputCursor, entryBlock);
91        PHINode* phiPreviousInputCursorPos = b->CreatePHI(b->getSizeTy(), 3);
92        phiPreviousInputCursorPos->addIncoming(inputCursor, entryBlock);
93        PHINode* phiPreviousBlockIndex = b->CreatePHI(b->getSizeTy(), 3);
94        phiPreviousBlockIndex->addIncoming(initBlockIndex, entryBlock);
95        PHINode* phiOutputCursorPos = b->CreatePHI(b->getSizeTy(), 3);
96        phiOutputCursorPos->addIncoming(initOutputCursor, entryBlock);
97
98
99
100        b->CreateCondBr(
101                b->CreateICmpULT(phiInputCursorPos, inputEndPos),
102                encodeBlockBody,
103                exitBlock
104        );
105
106        // ---- encodeBlockBody
107        b->SetInsertPoint(encodeBlockBody);
108
109        BasicBlock* updateCacheBlock = b->CreateBasicBlock("updateCacheBlock");
110        BasicBlock* extractMatchInfoBlock = b->CreateBasicBlock("extractMatchInfoBlock");
111
112        Value* newBlockIndex = b->CreateUDiv(phiInputCursorPos, SIZE_64);
113        b->CreateCondBr(
114                b->CreateICmpNE(newBlockIndex, phiPreviousBlockIndex),
115                updateCacheBlock,
116                extractMatchInfoBlock
117        );
118
119        // ---- updateCacheBlock
120        b->SetInsertPoint(updateCacheBlock);
121        this->updateCache(b, phiPreviousBlockIndex, initBlockIndex);
122        b->CreateBr(extractMatchInfoBlock);
123
124        // ---- encodeProcessBlock
125        b->SetInsertPoint(extractMatchInfoBlock);
126        MatchInfo retMatchInfo = this->extractMatchInfo(b, phiInputCursorPos, initBlockIndex, inputEndPos);
127//        b->CallPrintInt("matchLength", retMatchInfo.matchLength);
128        BasicBlock* noAppendOutputBlock = b->CreateBasicBlock("noAppendOutputBlock");
129        BasicBlock* appendOutputBlock = b->CreateBasicBlock("appendOutputBlock");
130
131        b->CreateCondBr(
132                b->CreateICmpUGE(
133                    retMatchInfo.matchLength,
134                    b->getSize(9)
135                ),
136                appendOutputBlock,
137                noAppendOutputBlock
138        );
139
140        // ---- appendOutputBlock
141        b->SetInsertPoint(appendOutputBlock);
142
143        Value* outputCursorPosAfterLiteral = this->appendLiteralSequence(b, phiPreviousInputCursorPos, phiInputCursorPos, phiOutputCursorPos);
144        Value* outputCursorPosAfterMatch = this->appendMatchSequence(b, retMatchInfo, outputCursorPosAfterLiteral);
145        Value* nextCursorPos = b->CreateAdd(phiInputCursorPos, retMatchInfo.matchLength);
146
147        phiInputCursorPos->addIncoming(nextCursorPos, b->GetInsertBlock());
148        phiPreviousInputCursorPos->addIncoming(nextCursorPos, b->GetInsertBlock());
149        phiPreviousBlockIndex->addIncoming(newBlockIndex, b->GetInsertBlock());
150        phiOutputCursorPos->addIncoming(outputCursorPosAfterMatch, b->GetInsertBlock());
151        b->CreateBr(encodeBlockCon);
152
153
154        // ---- noAppendOutputBlock
155        b->SetInsertPoint(noAppendOutputBlock);
156
157        Value* newInputCursorPos = b->CreateSelect(
158                b->CreateICmpEQ(phiPreviousInputCursorPos, phiInputCursorPos),
159                b->CreateAdd(phiInputCursorPos, b->getSize(8)),
160                b->CreateAdd(phiInputCursorPos, b->getSize(1))
161        );
162        newInputCursorPos = b->CreateUMin(newInputCursorPos, inputEndPos);
163
164        phiInputCursorPos->addIncoming(newInputCursorPos, b->GetInsertBlock());
165        phiPreviousInputCursorPos->addIncoming(phiPreviousInputCursorPos, b->GetInsertBlock());
166        phiPreviousBlockIndex->addIncoming(newBlockIndex, b->GetInsertBlock());
167        phiOutputCursorPos->addIncoming(phiOutputCursorPos, b->GetInsertBlock());
168        b->CreateBr(encodeBlockCon);
169
170        // ---- exitBlock
171        b->SetInsertPoint(exitBlock);
172
173
174        Value* finalOutputPos = this->appendLiteralSequence(b, phiPreviousInputCursorPos, inputEndPos, phiOutputCursorPos);
175        Value* blockSize = b->CreateSub(finalOutputPos, initOutputCursor);
176//        blockSizePos
177        Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream", b->getSize(0)), b->getInt8Ty()->getPointerTo());
178        b->CreateStore(b->CreateTrunc(blockSize, b->getInt32Ty()), b->CreatePointerCast(b->CreateGEP(outputBasePtr, b->CreateURem(blockSizePos, b->getCapacity("outputStream"))), b->getInt32Ty()->getPointerTo()));
179
180        b->setProducedItemCount("outputStream", finalOutputPos);
181
182    }
183
184    void LZParabixCompressionKernel::updateCache(const std::unique_ptr<KernelBuilder> &b, llvm::Value *i64BlockGlobalIndex, llvm::Value *initBlockGlobalIndex) {
185        // Constant
186        ConstantInt* SIZE_64 = b->getSize(64);
187        ConstantInt* INT_64_16 = b->getInt64(16);
188        ConstantInt* INT_32_8 = b->getInt32(8);
189
190        // Type
191        Type* i64PtrTy = b->getInt64Ty()->getPointerTo();
192        Type* i32PtrTy = b->getInt32Ty()->getPointerTo();
193
194        Value* localI64BlockIndex = b->CreateSub(i64BlockGlobalIndex, initBlockGlobalIndex);
195
196
197        Value* inputBasePtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
198
199        Value* startPos = b->CreateMul(i64BlockGlobalIndex, SIZE_64);
200        for (unsigned i = 0; i + 4 < 64; ++i) {
201            Value* targetPos = b->CreateAdd(startPos, b->getSize(i));
202            Value* valuePtr = b->CreatePointerCast(b->CreateGEP(inputBasePtr, targetPos), i32PtrTy);
203            Value* inputValue = b->CreateLoad(valuePtr);
204
205            Value* hashedKey = this->hashKey(b, inputValue);
206
207            // Update mStrToBlockIndex
208            Value* strToBlockIndexBasePtr = b->CreatePointerCast(b->getScalarFieldPtr("strToBlockIndex"), i64PtrTy);
209            Value* strToBlockIndexTargetPtr = b->CreateGEP(strToBlockIndexBasePtr, hashedKey);
210            Value* newBlockIndexCacheValue = b->CreateOr(b->CreateShl(b->CreateLoad(strToBlockIndexTargetPtr), INT_64_16), localI64BlockIndex);
211            b->CreateStore(newBlockIndexCacheValue, strToBlockIndexTargetPtr);
212
213            // Update mStrToMatchPos
214            Value* strToMatchPosBasePtr = b->CreatePointerCast(b->getScalarFieldPtr("strToMatchPos"), i32PtrTy);
215            Value* strToMatchPosTargetPtr = b->CreateGEP(strToMatchPosBasePtr, hashedKey);
216            Value* newMatchPosCacheValue = b->CreateOr(b->CreateShl(b->CreateLoad(strToMatchPosTargetPtr), INT_32_8), b->getInt32(i));
217            b->CreateStore(newMatchPosCacheValue, strToMatchPosTargetPtr);
218        }
219    }
220
221    llvm::Value *LZParabixCompressionKernel::hashKey(const std::unique_ptr<KernelBuilder> &b, llvm::Value *v) {
222        //  (((v) * 2654435761U) >> ((4 * 8) - HASHLOG))
223        ConstantInt* magicNumber = b->getInt32(2654435761); // 2654435761 here is a Magic Number for hash
224        return b->CreateLShr(
225                b->CreateMul(v, magicNumber),
226                b->getInt32(4 * 8 - HASHLOG)
227        );
228    }
229
230
231
232    MatchInfo LZParabixCompressionKernel::extractMatchInfo(const std::unique_ptr<KernelBuilder> &b, llvm::Value *cursorPos, llvm::Value *initBlockGlobalIndex, llvm::Value* inputEndPos) {
233        // ---- EntryBlock
234        Value* SIZE_0 = b->getSize(0);
235        MatchInfo retInfo = {SIZE_0, SIZE_0, SIZE_0, SIZE_0};
236
237        BasicBlock* entryBlock = b->GetInsertBlock();
238        BasicBlock* exitBlock = b->CreateBasicBlock("exitBlock");
239
240        Value* inputBasePtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
241
242        auto retMatchInfo = this->getPossibleMatchInfo(b, cursorPos);
243
244        Value* possibleBlockIndexes = retMatchInfo.first;
245        Value* possibleMatchPos = retMatchInfo.second;
246
247        Value* currentGlobalInputBlockIndex = b->CreateUDiv(cursorPos, b->getSize(64));
248
249        for (unsigned i = 0; i < 4; i++) {
250            BasicBlock* extractMatchInfoEntryBlock = b->CreateBasicBlock("extractMatchInfoEntryBlock");
251            b->CreateBr(extractMatchInfoEntryBlock);
252
253            // ---- extractMatchInfoEntryBlock
254            b->SetInsertPoint(extractMatchInfoEntryBlock);
255
256            Value* localMatchBlockIndex = b->CreateAnd(b->CreateLShr(possibleBlockIndexes, b->getInt64(i * 16)), b->getInt64(0xffff));
257            Value* globalMatchBlockIndex = b->CreateAdd(localMatchBlockIndex, initBlockGlobalIndex);
258
259            Value* matchPos = b->CreateAnd(b->CreateLShr(possibleMatchPos, b->getInt32(i * 8)), b->getInt32(0xff));
260            matchPos = b->CreateZExt(matchPos, b->getInt64Ty());
261
262            Value* blockOffset = b->CreateSub(currentGlobalInputBlockIndex, globalMatchBlockIndex);
263
264            Value* isNoMatch = b->CreateOr(
265                    b->CreateICmpUGE(globalMatchBlockIndex, currentGlobalInputBlockIndex),
266                    b->CreateICmpUGE(blockOffset, b->getSize(128))
267            );
268
269//            b->CallPrintInt("isNoMatch", isNoMatch);
270
271            BasicBlock* scanMatchConBlock = b->CreateBasicBlock("scanMatchConBlock");
272            BasicBlock* scanMatchExitBlock = b->CreateBasicBlock("scanMatchExitBlock");
273
274//            b->CreateCondBr(isNoMatch, scanMatchExitBlock, scanMatchConBlock);
275            b->CreateBr(scanMatchConBlock);
276
277            // ---- scanMatchConBlock
278            b->SetInsertPoint(scanMatchConBlock);
279            PHINode* phiForwardMatchLength = b->CreatePHI(b->getSizeTy(), 2);
280            phiForwardMatchLength->addIncoming(b->getSize(0), extractMatchInfoEntryBlock);
281            PHINode* phiMatchPos = b->CreatePHI(b->getSizeTy(), 2);
282            phiMatchPos->addIncoming(matchPos, extractMatchInfoEntryBlock);
283            PHINode* phiMatchMask = b->CreatePHI(b->getInt64Ty(), 2);
284            phiMatchMask->addIncoming(b->getInt64(0), extractMatchInfoEntryBlock);
285
286            Value* isMatch = b->CreateICmpEQ(
287                    b->CreateLoad(b->CreateGEP(inputBasePtr, b->CreateAdd(b->CreateMul(globalMatchBlockIndex, b->getInt64(64)), phiMatchPos))),
288                    b->CreateLoad(b->CreateGEP(inputBasePtr, b->CreateAdd(cursorPos, phiForwardMatchLength)))
289            );
290
291            phiForwardMatchLength->addIncoming(
292                    b->CreateSelect(isMatch, b->CreateAdd(phiForwardMatchLength, b->getSize(1)), phiForwardMatchLength),
293                    b->GetInsertBlock()
294            );
295            phiMatchPos->addIncoming(
296                    b->CreateAdd(phiMatchPos, b->getSize(1)),
297                    b->GetInsertBlock()
298            );
299
300            phiMatchMask->addIncoming(
301                    b->CreateSelect(
302                            isMatch,
303                            b->CreateOr(phiMatchMask, b->CreateShl(b->getInt64(1), phiMatchPos)),
304                            phiMatchMask
305                    ),
306                    b->GetInsertBlock()
307            );
308
309            b->CreateCondBr(
310                    b->CreateAnd(
311                            b->CreateAnd(
312                                    b->CreateICmpULT(phiMatchPos, b->getInt64(64)),
313                                    b->CreateICmpULT(b->CreateAdd(cursorPos, phiForwardMatchLength), inputEndPos)
314                            ),
315                            b->CreateNot(isNoMatch)
316                    ),
317                    scanMatchConBlock,
318                    scanMatchExitBlock
319            );
320
321            // ---- scanMatchExitBlock
322            b->SetInsertPoint(scanMatchExitBlock);
323
324            Value* isBetterMatch = b->CreateICmpUGT(phiForwardMatchLength, retInfo.matchLength);
325            retInfo.matchLength = b->CreateSelect(isBetterMatch, phiForwardMatchLength, retInfo.matchLength);
326            retInfo.matchMask = b->CreateSelect(isBetterMatch, phiMatchMask, retInfo.matchMask);
327            retInfo.matchOffset = b->CreateSelect(isBetterMatch, blockOffset, retInfo.matchOffset);
328            retInfo.matchStart = b->CreateSelect(isBetterMatch, cursorPos, retInfo.matchOffset);
329
330            // TODO search back and adjust match start
331        }
332        b->CreateBr(exitBlock);
333        b->SetInsertPoint(exitBlock);
334
335        return retInfo;
336
337    }
338
339    std::pair<llvm::Value *, llvm::Value *>
340    LZParabixCompressionKernel::getPossibleMatchInfo(const std::unique_ptr<KernelBuilder> &b, llvm::Value *cursorPos) {
341        // Type
342        Type* i64PtrTy = b->getInt64Ty()->getPointerTo();
343        Type* i32PtrTy = b->getInt32Ty()->getPointerTo();
344
345        Value* inputBasePtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", b->getSize(0)), b->getInt8PtrTy());
346        Value* targetPtr = b->CreateGEP(inputBasePtr, cursorPos);
347        targetPtr = b->CreatePointerCast(targetPtr, b->getInt32Ty()->getPointerTo());
348        Value* hashedKey = this->hashKey(b, b->CreateLoad(targetPtr));
349//        b->CallPrintInt("hashedKey", hashedKey);
350        Value* strToBlockIndexBasePtr = b->CreatePointerCast(b->getScalarFieldPtr("strToBlockIndex"), i64PtrTy);
351        Value* strToBlockIndexTargetPtr = b->CreateGEP(strToBlockIndexBasePtr, hashedKey);
352
353        Value* strToMatchPosBasePtr = b->CreatePointerCast(b->getScalarFieldPtr("strToMatchPos"), i32PtrTy);
354        Value* strToMatchPosTargetPtr = b->CreateGEP(strToMatchPosBasePtr, hashedKey);
355
356        return std::make_pair(
357                b->CreateLoad(strToBlockIndexTargetPtr),
358                b->CreateLoad(strToMatchPosTargetPtr)
359        );
360    }
361
362    Value *LZParabixCompressionKernel::appendLiteralSequence(const unique_ptr<KernelBuilder> &b, Value *literalStart,
363                                                             Value *literalEnd, Value *outputPos) {
364        // Constant
365        Value* SIZE_0 = b->getSize(0);
366        Value* SIZE_1 = b->getSize(1);
367        Value* SIZE_64 = b->getSize(64);
368        Type* i8PtrTy = b->getInt8PtrTy();
369
370
371        Value* inputBasePtr = b->CreatePointerCast(b->getRawInputPointer("byteStream", SIZE_0), i8PtrTy);
372        Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream", SIZE_0), i8PtrTy);
373        Value* outputCapacity = b->getCapacity("outputStream");
374
375
376        // ---- EntryBlock
377        BasicBlock* entryBlock = b->GetInsertBlock();
378        BasicBlock* appendLiteralConBlock = b->CreateBasicBlock("AppendLiteralConBlock");
379        BasicBlock* appendLiteralBodyBlock = b->CreateBasicBlock("AppendLiteralBodyBlock");
380        BasicBlock* appendLiteralExitBlock = b->CreateBasicBlock("AppendLiteralExitBlock");
381
382        b->CreateBr(appendLiteralConBlock);
383
384        // ---- AppendLiteralConBlock
385        b->SetInsertPoint(appendLiteralConBlock);
386        PHINode* phiOutputPos = b->CreatePHI(b->getSizeTy(), 2);
387        phiOutputPos->addIncoming(outputPos, entryBlock);
388        PHINode* phiLiteralStart = b->CreatePHI(b->getSizeTy(), 2);
389        phiLiteralStart->addIncoming(literalStart, entryBlock);
390
391        Value* remainingLiteralLength = b->CreateSub(literalEnd, phiLiteralStart);
392
393        b->CreateCondBr(b->CreateICmpUGT(remainingLiteralLength, b->getSize(0)), appendLiteralBodyBlock, appendLiteralExitBlock);
394
395        // ---- AppendLiteralBodyBlock
396        b->SetInsertPoint(appendLiteralBodyBlock);
397
398        Value* outputPosRem = b->CreateURem(phiOutputPos, outputCapacity);
399        Value* outputNextPosRem = b->CreateAdd(outputPosRem, b->getSize(1));
400
401        Value* maxLiteralLength = b->CreateSub(SIZE_64, b->CreateURem(outputNextPosRem, SIZE_64));
402        Value* literalLength = b->CreateUMin(remainingLiteralLength, maxLiteralLength);
403
404        Value* literalToken = b->CreateOr(b->CreateTrunc(literalLength, b->getInt8Ty()), b->getInt8(1 << 7));
405
406        b->CreateStore(literalToken, b->CreateGEP(outputBasePtr, outputPosRem));
407        b->CreateMemCpy(
408                b->CreateGEP(outputBasePtr, outputNextPosRem),
409                b->CreateGEP(inputBasePtr, phiLiteralStart),
410                literalLength,
411                1
412        );
413
414        phiLiteralStart->addIncoming(b->CreateAdd(phiLiteralStart, literalLength), b->GetInsertBlock());
415        phiOutputPos->addIncoming(b->CreateAdd(phiOutputPos, b->CreateAdd(literalLength, SIZE_1)), b->GetInsertBlock());
416        b->CreateBr(appendLiteralConBlock);
417
418        // ---- AppendLiteralExitBlock
419        b->SetInsertPoint(appendLiteralExitBlock);
420
421        return phiOutputPos;
422    }
423
424    Value* LZParabixCompressionKernel::appendMatchSequence(const unique_ptr<KernelBuilder> &b, const MatchInfo& matchInfo, Value* outputPos) {
425        // Constant
426        Value* SIZE_0 = b->getSize(0);
427        Value* SIZE_1 = b->getSize(1);
428        Value* SIZE_64 = b->getSize(64);
429        Type* i8PtrTy = b->getInt8PtrTy();
430
431        Value* outputBasePtr = b->CreatePointerCast(b->getRawOutputPointer("outputStream", SIZE_0), i8PtrTy);
432        Value* outputCapacity = b->getCapacity("outputStream");
433
434        // MatchOffset
435        b->CreateStore(b->CreateTrunc(matchInfo.matchOffset, b->getInt8Ty()), b->CreateGEP(outputBasePtr, b->CreateURem(outputPos, outputCapacity)));
436
437        Value* outputOneBitIndexPos = b->CreateAdd(outputPos, SIZE_1);
438        Value* outputZeroBitIndexPos = b->CreateAdd(outputOneBitIndexPos, SIZE_1);
439
440        Value* outputBitMaskPos = b->CreateAdd(outputZeroBitIndexPos, SIZE_1);
441
442        Value* oneBitIndex = b->getInt8(0);
443        Value* zeroBitIndex = b->getInt8(0);
444
445        for (unsigned i = 0; i < 8; i++) {
446            Value* currentBitIndex = b->CreateTrunc(b->CreateLShr(matchInfo.matchMask, b->getInt64(i * 8)), b->getInt8Ty());
447            Value* newOneBit = b->CreateICmpEQ(currentBitIndex, b->getInt8(0xff));
448            Value* newZeroBit = b->CreateICmpEQ(currentBitIndex, b->getInt8(0));
449
450            oneBitIndex = b->CreateSelect(
451                    newOneBit,
452                    b->CreateOr(oneBitIndex, b->getInt8(1 << i)),
453                    oneBitIndex
454            );
455
456            zeroBitIndex = b->CreateSelect(
457                    newZeroBit,
458                    b->CreateOr(zeroBitIndex, b->getInt8(1 << i)),
459                    zeroBitIndex
460            );
461            b->CreateStore(currentBitIndex, b->CreateGEP(outputBasePtr, b->CreateURem(outputBitMaskPos, outputCapacity)));
462            outputBitMaskPos = b->CreateSelect(
463                    b->CreateOr(newOneBit, newZeroBit),
464                    outputBitMaskPos,
465                    b->CreateAdd(outputBitMaskPos, SIZE_1)
466            );
467        }
468        b->CreateStore(oneBitIndex, b->CreateGEP(outputBasePtr, b->CreateURem(outputOneBitIndexPos, outputCapacity)));
469        b->CreateStore(zeroBitIndex, b->CreateGEP(outputBasePtr, b->CreateURem(outputZeroBitIndexPos, outputCapacity)));
470
471        return outputBitMaskPos;
472    }
473
474}
Note: See TracBrowser for help on using the repository browser.