fix: prevent batch_index overflow in raw_curp

[GFX9]

• what problem are you trying to solve? (or if there's no problem, what's the motivation for this change?) -> Fixes #368

• what changes does this pull request make? -> Use a scrolling array to replace the previous prefix array to prevent batch_index overflow, which will be truncated when compact. Besides, the scrolling array reduces the operation time complexity of obtaining batch log to O(1).

• are there any non-obvious implications of these changes? (does it break compatibility with previous versions, etc) -> No

[codecov[bot]]

Codecov Report

Attention: Patch coverage is 89.41176% with 9 lines in your changes are missing coverage. Please review.

Project coverage is 75.61%. Comparing base (e35b35a) to head (55442ec). Report is 49 commits behind head on master.

Files	Patch %	Lines
crates/curp/src/server/raw_curp/log.rs	89.41%	3 Missing and 6 partials :warning:

Additional details and impacted files

@@            Coverage Diff             @@
##           master     #704      +/-   ##
==========================================
+ Coverage   75.55%   75.61%   +0.06%     
==========================================
  Files         180      187       +7     
  Lines       26938    27614     +676     
  Branches    26938    27614     +676     
==========================================
+ Hits        20353    20881     +528     
- Misses       5366     5450      +84     
- Partials     1219     1283      +64     

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[bsbds]

This implementation is too complex compare to the original prefix sum version. I suggest making some modifications to the original algorithm. Here's the pseudocode. The interval representation is [left, right).

#[derive(Default)]
struct Log {
    right: Vec<usize>,
    sizes: Vec<u64>,
    limit: u64,
    p: usize,
    sum: u64,
}

impl Log {
    fn push(&mut self, size: u64) {
        self.sizes.push(size);
        self.right.push(0);
        self.sum += size;
        while self.sum > self.limit {
            self.right[self.p] = self.sizes.len() - 1;
            self.sum -= self.sizes[self.p];
            self.p += 1;
        }
    }

    fn get(&self, left: usize) -> usize {
        self.right[left]
    }
}

[mergify[bot]]

@GFX9 Convert your pr to draft since CI failed

[mergify[bot]]

@GFX9 Convert your pr to draft since CI failed

[mergify[bot]]

@GFX9 Convert your pr to draft since CI failed

[GFX9]

The current implementation uses relevant offset to handle the right index of the range. But when Log calls methods of LogEntryVecDeque, there already exists the process of transferring the logical index to physical index. So the current implementation is kind of redundant, which should be improved in the future.

[Phoenix500526]

@Mergifyio rebase

[mergify[bot]]

rebase

✅ Branch has been successfully rebased