Skip to content

Instantly share code, notes, and snippets.

@maketubo
Last active September 8, 2020 15:55
Show Gist options
  • Save maketubo/2478cede251b1b99c31088a8f4fc7160 to your computer and use it in GitHub Desktop.
Save maketubo/2478cede251b1b99c31088a8f4fc7160 to your computer and use it in GitHub Desktop.
My FindByte Implementation
public class FindByte {
static Map<Byte, Long> map = new HashMap<>();
public static List<Integer> findAllPer8(byte find, byte[] target){
List<Integer> list = new ArrayList<>();
for(int i = 0; i < target.length; i = i + 8){
byte[] array;
if(target.length - i < 8){
array = Arrays.copyOfRange(target, i, target.length);
} else {
array = Arrays.copyOfRange(target, i, i + 8);
}
int index = findFirstIn8(find, array);
if(index != -1){
list.add(i + index);
}
}
return list;
}
public static int findFirst(byte find, byte[] target){
int index = -1;
for(int i = 0; i < target.length; i = i + 8){
byte[] array;
if(target.length - i < 8){
array = Arrays.copyOfRange(target, i, target.length);
} else {
array = Arrays.copyOfRange(target, i, i + 8);
}
index = findFirstIn8(find, array);
if(index != -1){
return i + index;
}
}
return index;
}
public static int findFirstIn8(byte find, byte[] target){
if(target.length < 8){
for(int i = 0; i < target.length; i++){
if(target[i] == find) {
return i;
}
}
}
int result = firstFirstIn8(getWord(target, 0), compilePattern(find));
return result < 8 ? result : -1;
}
private static long getWord(byte[] data, int index) {
//用小字节序反而有问题ByteOrder.LITTLE_ENDIAN
ByteBuffer wrap = ByteBuffer.wrap(data);
long value = wrap.getLong(index);
wrap.clear();
return value;
}
private static long compilePattern(byte byteToFind) {
Long longToFind = map.get(byteToFind);
if(longToFind != null){
return longToFind;
}
//高位缺位补0
long pattern = byteToFind & 0xFFL;
pattern = pattern
| (pattern << 8)
| (pattern << 16)
| (pattern << 24)
| (pattern << 32)
| (pattern << 40)
| (pattern << 48)
| (pattern << 56);
map.put(byteToFind, pattern);
//每byte都置为相同的byteToFind
return pattern;
}
private static int firstFirstIn8(long word, long pattern) {
// 异或 1字节 = 8 bit / long 64 bit
long input = word ^ pattern;
long tmp = (input & 0x7F7F7F7F7F7F7F7FL) + 0x7F7F7F7F7F7F7F7FL;
tmp = ~(tmp | input | 0x7F7F7F7F7F7F7F7FL);
return Long.numberOfLeadingZeros(tmp) >>> 3;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment