求识别：1-8字节转1-7字节的位操作算法是否为已知算法？

问题概述 #

正在还原一个程序，该程序可将1-8字节的输入转换为1-7字节的输出，核心为位操作，但无法确定完整算法逻辑。

已实现的位操作方法 #

public byte ChangeMSB(byte input)
{
    byte[] output = { 0x00 };
    var bits = new BitArray(new byte[] { input });
    bits.Set(bits.Length - 1, true);
    bits.CopyTo(output, 0);
    return output[0];
}

public byte RightShiftBits(byte input, int count)
{
    byte[] output = { 0x00 };
    var bits = new BitArray(new byte[] { input });
    bits.RightShift(count);
    bits.CopyTo(output, 0);
    return output[0];
}

public byte LeftShiftBits(byte input, int count)
{
    byte[] output = { 0x00 };
    var bits = new BitArray(new byte[] { input });
    bits.LeftShift(count);
    bits.CopyTo(output, 0);
    return output[0];
}

public byte OrBits(byte firstByte, byte secondByte)
{
    byte[] ORed = { 0x00 };
    var firstBits = new BitArray(new byte[] { firstByte });
    var secondBits = new BitArray(new byte[] { secondByte });
    var ORedBits = firstBits.Or(secondBits);
    ORedBits.CopyTo(ORed, 0);
    return ORed[0];
}

尝试的两个适配算法 #

算法1：Try #

public byte[] Try(byte[] input)
{
    byte[] output;
    switch (input.Length)
    {
        case 1:
            return input;
        case 8:
            output = new byte[input.Length - 1];
            break;
        default:
            output = new byte[input.Length];
            break;
    }
    Array.Copy(input, output, output.Length);
    for (int i = 0; i < output.Length; i++)
    {
        if (i != output.Length - 1)
        {
            output[i] = ChangeMSB(output[i]);
        }
        output[i] = RightShiftBits(output[i], i);
        if (i + 1 != output.Length && !input[i].Equals(input[i + 1]))
        {
            output[i] = ChangeMSB(output[i]);
        }
        if (i == 6 && input.Length == 8)
        {
            output[i] = OrBits(output[i], LeftShiftBits(input[input.Length - 1], 1));
            break;
        }
    }
    return output;
}

算法2：Try2 #

public byte[] Try2(byte[] input)
{
    byte[] output;
    switch (input.Length)
    {
        case 1:
            return input;
        case 8:
            output = new byte[input.Length - 1];
            break;
        default:
            output = new byte[input.Length];
            break;
    }
    Array.Copy(input, output, output.Length);
    for (int i = 0; i < output.Length; i++)
    {
        int operation = 0;
        for (int j = i; j > 0; j--)
        {
            if (i > 0)
            {
                operation = (int)output[i] / 2;
                output[i] = (byte)operation;
            }
            
            if (IsOdd(output[i]) && i != output.Length - 1)
            {
                output[i] = ChangeMSB(output[i]);
            }
        }
        output[0] = ChangeMSB(output[0]);
        if (i == 6 && input.Length == 8)
        {
            operation = (int)output[i] + input[input.Length - 1] * 2;
            output[i] = (byte)operation;
            break;
        }
    }
    return output;
}

已发现的转换规律 #

• output数组中每个元素右移“索引”位，若非最后一个元素，还会根据未知条件修改部分位；
• 当输入为8字节时，output[6]满足：

output[6] = OrBits(RightShiftBits(input[6], 6), LeftShiftBits(input[7], 1)) or (int)input[6]/2^6 + (int)input[7]*2;

原程序测试用例（编码：GSM 7-bit默认字母表） #

input = 41 (A) | output = 41;
input = 41 41 (AA) | output = C1 20;
input = 41 41 41 (AAA) | output = C1 60 10;
input = 41 42 43 44 45 46 47 (ABCDEFG) | output = 41 E1 90 58 34 1E 01;
input = 41 42 43 44 45 46 47 48 (ABCDEFGH) | output = 41 E1 90 58 34 1E 91;
input = 48 47 46 45 44 43 42 41 (HGFEDCBA) | output = C8 A3 B1 48 1C 0A 83;
input = 4D 43 4B (MCK) | output = CD E1 12;

当前算法输出结果 #

output = 41;
output = C1 20;
output = C1 60 10;
output = C1 E1 B0 98 8C 86 01;
output = C1 E1 B0 98 8C 86 91;
output = C8 E3 B1 98 8C 86 83;
output = CD E1 12;

疑问 #

1. 该转换逻辑是否为已知算法？
2. 如何完善现有算法以适配所有测试用例？

内容的提问来源于stack exchange，提问作者Schala_Zeal