Prevent packets from having dangerously sized collections (Part 2)

[Protonull]

I'm looking to reopen #110 but I've noticed some more potential for optimisation.

For context, this is the current negotiation (excluding the size of the dimension identifier):

• Server►Client: ClientboundRegionTimestampsPacket:
  • region count (u16):
    • regionX (u16)
    • regionZ (u16)
    • timestamp (u64)
• Server◄Client: ServerboundChunkTimestampsRequestPacket:
  • region count (u16):
    • regionX (u16)
    • regionZ (u16)
• Server►Client: ClientboundChunkTimestampsResponsePacket:
  • chunk count (u32):
    • chunkX (u32)
    • chunkZ (u32)
    • timestamp (u64)
• Server◄Client: ServerboundCatchupRequestPacket:
  • chunk count (u32):
    • chunkX (u32)
    • chunkZ (u32)
    • timestamp (u64)

Funnily enough, while the first two are problematic, they'll never be a problem on CivMC due to the relatively small size of the world: CivMC has a squared-out world size of 20000x20000, which is 40x40 or 1600 regions, which surprisingly only results in 19200 bytes of data. This would comfortably fit even if the recent max-frame-size changes were reverted back down to 65535 bytes.

No, the issue lies with the latter two packets: each region has 32x32 or 1024 chunks, which results in 16384 bytes of data. It only took 4 region's worth of data to exhaust the former maximum frame size... no wonder it was causing issues. While the recently increased (#114) maximum improves things, it only increases that limit to 64 regions, which is still a far cry from 1600. The problem is not the frame size, it's the protocol itself.

As a solution, my plan is to limit the scope of each ClientboundChunkTimestampsResponsePacket and ServerboundCatchupRequestPacket to a single region. This would trade total packet size with packet frequency. There are a number of strategies for this though:

Strategy A: Logic Change

Nothing about the packet itself will be changed, but the data it represents would be limited to a single region.

Chunk Count	Bytes
1	20
1,024	16,388

Strategy B: Chunk Keys

This involves update the packet to include the region coordinate, and then using internal chunk coordinates. This offers a pretty substantial reduction in size.

• Server►Client: ClientboundChunkTimestampsResponsePacket:
  • regionX (u16)
  • regionZ (u16)
  • chunk count (u16):
    • chunkX (u8)
    • chunkZ (u8)
    • timestamp (u64)

Chunk Count	Bytes	Comparison (Strategy A)
1	13	35.00% smaller
1,024	10,244	37.49% smaller

Strategy C: Chunks BitSet

This would likewise involve updating the packet to include the region coordinate, but would instead use a 'chunks bitset': a 32x32 grid of 1bit booleans. After that would be a list of timestamps whose length corresponds to the number of 1s in the bitset, which correspond to each chunk in order of appearance.

• Server►Client: ClientboundChunkTimestampsResponsePacket:
  • regionX (u16)
  • regionZ (u16)
  • chunks bitset (u1024)
    • timestamp (u64)

Chunk Count	Bytes	Comparison (Strategy A)	Comparison (Strategy B)
1	140	600.00% larger	976.92% larger
1,024	8,324	49.20% smaller	18.74% smaller

Dilemma

I think we can all agree that Strategy A is out of the question, but the issue is choosing between Strategy B and C. It takes only 64 chunk timestamps for Strategy C to become more space efficient than Strategy B, which is not at all difficult to achieve given CivMC's render distance: travelling in a straight line (eg: riding a rail) through a region would load 15x32 or 480 chunks. That said, barely 'discovered' regions (such as those with only a couple chunks in their corners filled in) would be significantly smaller with Strategy B.

Strategy C has the benefit of obviating the possibility of duplicates (where a chunk is given two or more timestamps), though I don't believe this has been an issue to date. Counter point: Strategy C is significantly more complex, particularly since Java's BitSet is pretty unhelpful since it's copy-only and can expand in size, and thus may require additional dependencies on the client and server side to ease friction and keep the code somewhat readable.

Thoughts?