Welcome, guest! Please login or register.

    * Shoutbox

    RefreshHistory
    • AutoScapeM: Join autoscape,0rg fun events daily for infernal mystery boxes only server with Infernal Twisted Bow
      September 19, 2019, 11:57:33 PM
    • AutoScapeM: Join autoscape,0rg fun events daily for infernal mystery boxes only server with Infernal Twisted Bow
      September 19, 2019, 11:57:30 PM
    • AutoScapeM: Join autoscape,0rg fun events daily for infernal mystery boxes only server with Infernal Twisted Bow
      September 19, 2019, 11:57:25 PM
    • AutoScapeM: Join autoscape,0rg fun events daily for infernal mystery boxes only server with Infernal Twisted Bow
      September 19, 2019, 11:57:19 PM
    • PavSwag: try autoscape,0rg today i will personally help you get RICH and well KNOWN - pav
      September 19, 2019, 12:36:06 PM
    • PavSwag: try autoscape,0rg today i will personally help you get RICH and well KNOWN - pav
      September 19, 2019, 12:35:49 PM
    • Codar: Come join us while we're fresh we're growing fast!! @ [link]
      September 18, 2019, 09:30:25 PM
    • Codar: New RSPS come check us out! @ [link]
      September 18, 2019, 04:07:24 AM
    • Codar: Released a new server come check us out! @ [link]
      September 18, 2019, 02:08:23 AM
    • ragnoroker: RuneGuild will be hosting some tournaments later to win some mystery boxes, join here : [link]
      September 16, 2019, 09:50:10 AM
    • calemx: death's-server has officially been released, come check us out  - [link]
      September 13, 2019, 04:14:21 AM
    • PavSwag: try autoscape,0rg today i will personally help you get RICH and well KNOWN - pav
      September 12, 2019, 12:26:40 PM
    • cbrophy: would my account from 2013 work?
      September 12, 2019, 05:04:43 AM
    • ragnoroker: RuneGuild has officially been released, come check us out - [link]
      September 11, 2019, 11:26:35 AM
    • ragnoroker: RuneGuild has officially been released, come check us out - [link]
      September 11, 2019, 11:26:31 AM
    • ragnoroker: RuneGuild is due to be released tomorrow! First few players will recieve some goodies. Sign up on our website [link] Join our discord for updates [link]
      September 07, 2019, 07:43:28 PM
    • ragnoroker: RuneGuild is due to be released tomorrow! First few players will recieve some goodies. Sign up on our website [link] Join our discord for updates [link]
      September 07, 2019, 07:42:59 PM
    • ChrisMeadows: Yo, what's the forum's discord?
      September 04, 2019, 08:33:06 PM
    • newerarsps: i cannot register to rsps list anyone can help?
      September 01, 2019, 11:24:00 PM
    • PavSwag: Date Registered: July 03, 2012, 03:54:45 PM Think im just as good vet as u man, + I have over 80B in rs3 think im good on anyones 100k ass lookin bank b oi
      August 27, 2019, 10:48:09 AM

    Author Topic: Virtual file cache indexing  (Read 2734 times)

    0 Members and 1 Guest are viewing this topic.

    Offline_nova

    • Member
    • **
    • Posts: 31
    • Thanks: +10/-10
      • View Profile
    Virtual file cache indexing
    « on: April 28, 2016, 04:32:57 AM »
    It's known that the Runescape cache structure has a single data file and a bunch of files which are pointers to the first chunk of a file, and the length of the file. The purpose of these file indexes is so that the client has O(1) lookup on entries on the cache, although the fact may not be apparent. In the newer engines which has a compressed container format, you actually can remove the need for a file index (unless you want to save memory) and build a virtual file index by analyzing the data file. Here's an implementation of that, just for the sake of an example.

    I think for any cache library, this is much easier in terms of dependencies (you only need a single class to read files) and it makes the file structure easier to understand. The catch is that you MUST have a container like format which describes the packed length of the data, but all the files are already packed that way.

    It's also important to note that chunk 0 is denoted as the 'EOF' chunk so you can estimate file sizes within a margin of 512 bytes. Depending on how large you cache archive is rebuilding the virtual index can take a longer amount of time to start up but you could precalculate the indexes (like the client already does) and load those files into memory.

    This solution also works better for knowing which files are corrupted, and what files are actually included in the cache.

    You don't have to use morton codes for hashing, I just did out of preference. You can just encode the cache id (or type) and file id into a dword.

    Code: Java
    1. packagecom.evelus.jagexfs;
    2.  
    3. importcom.evelus.jagexfs.util.MortonCode;
    4. importcom.google.common.base.Preconditions;
    5.  
    6. importjava.io.IOException;
    7. importjava.io.RandomAccessFile;
    8. importjava.nio.BufferUnderflowException;
    9. importjava.nio.ByteBuffer;
    10. importjava.util.HashMap;
    11. importjava.util.HashSet;
    12. importjava.util.Map;
    13. importjava.util.Set;
    14.  
    15. /**
    16.  * @author hadyn
    17.  */
    18. publicclass EntryCache {
    19.   privateRandomAccessFile data;
    20.   privatefinalbyte[] CHUNK_BUFFER =newbyte[EntryChunk.LENGTH];
    21.   private Map<Integer, CachePointer> pointers =new HashMap<>();
    22.  
    23.   publicstaticlong compressedLength = 0L;
    24.   publicstaticlong uncompressedLength = 0L;
    25.  
    26.   public EntryCache(RandomAccessFile data)throwsIOException{
    27.     this.data= data;
    28.     rebuildIndex();
    29.   }
    30.  
    31.   /**
    32.    * Reads an entry container from the cache and extracts the data.
    33.    *
    34.    * @param type    the type.
    35.    * @param entryId the entry id.
    36.    * @return the unpacked container bytes for the entry.
    37.    * @throws IOException if an I/O exception was encountered while reading the container.
    38.    */
    39.   publicbyte[] unpackContainer(int type, int entryId)throwsIOException{
    40.     byte[] bytes = readContainer(type, entryId);
    41.     Container container =newContainer();
    42.     container.read(ByteBuffer.wrap(bytes));
    43.     return container.getBytes();
    44.   }
    45.  
    46.   /**
    47.    * Reads an entry container from the cache. To extract the bytes from the container it will
    48.    * have to be unpacked.
    49.    *
    50.    * @param type    the type.
    51.    * @param entryId the entry id.
    52.    * @return the container bytes.
    53.    * @throws IOException if an I/O exception was encountered while reading the container.
    54.    *
    55.    * @see Container
    56.    */
    57.   publicbyte[] readContainer(int type, int entryId)throwsIOException{
    58.     if(!containsEntry(type, entryId)){
    59.       returnnull;
    60.     }
    61.     CachePointer pointer = pointers.get(MortonCode.mortonCode2i(type, entryId));
    62.     int length = pointer.getLength();
    63.     byte[] bytes =newbyte[length];
    64.     int chunkId = pointer.getFirstChunk();
    65.     EntryChunk chunk =new EntryChunk();
    66.     int destOff =0;
    67.     int part =0;
    68.     while(chunkId != EntryChunk.EOF_CHUNK){
    69.       readChunk(chunk, chunkId);
    70.       if(chunk.getType()!= type || chunk.getEntryId()!= entryId || part != chunk.getPart()){
    71.         thrownewIOException("Corrupted file: "+ type +", "+ entryId +".");
    72.       }
    73.       int read = length - destOff;
    74.       if(read > EntryChunk.DATA_LENGTH){
    75.         read = EntryChunk.DATA_LENGTH;
    76.       }
    77.       if(chunk.getLength()< read){
    78.         thrownew BufferUnderflowException();
    79.       }
    80.       System.arraycopy(chunk.getData(), 0, bytes, destOff, read);
    81.       chunkId = chunk.getNextChunk();
    82.       destOff += read;
    83.       part++;
    84.     }
    85.     return bytes;
    86.   }
    87.  
    88.   privatevoid readChunk(EntryChunk chunk, int chunkId)throwsIOException{
    89.     Preconditions.checkArgument(chunkId > EntryChunk.EOF_CHUNK, "Invalid chunk id: %s.", chunkId);
    90.     Preconditions.checkState(chunkExists(chunkId), "Chunk does not exist: %s.", chunkId);
    91.     long position = chunkId *(long) EntryChunk.LENGTH;
    92.     int len =(int)Math.min(data.length()- position, EntryChunk.LENGTH);
    93.     data.seek(position);
    94.     data.read(CHUNK_BUFFER, 0, len);
    95.     chunk.read(ByteBuffer.wrap(CHUNK_BUFFER));
    96.   }
    97.  
    98.   privatevoid writeChunk(EntryChunk chunk, int chunkId)throwsIOException{
    99.     ByteBuffer bb = ByteBuffer.wrap(CHUNK_BUFFER);
    100.     chunk.write(bb);
    101.     bb.flip();
    102.     bb.get(CHUNK_BUFFER, 0, bb.limit());
    103.     data.seek(chunkId *(long) EntryChunk.LENGTH);
    104.     data.write(CHUNK_BUFFER, 0, bb.limit());
    105.   }
    106.  
    107.   privateint getFreeChunk()throwsIOException{
    108.     return size()+1;
    109.   }
    110.  
    111.   privateboolean chunkExists(int chunkId)throwsIOException{
    112.     return size()> chunkId;
    113.   }
    114.  
    115.   publicboolean containsEntry(int type, int entryId){
    116.     return pointers.containsKey(MortonCode.mortonCode2i(type, entryId));
    117.   }
    118.  
    119.   /**
    120.    * Rebuilds the index for the cache. This function will clear any other file pointers already
    121.    * associated with this cache.
    122.    *
    123.    * @throws IllegalArgumentException if there are multiple chunks which describe the start of a
    124.    *                                  file.
    125.    */
    126.   publicvoid rebuildIndex()throwsIOException{
    127.     pointers.clear();
    128.  
    129.     Set<Integer> hashes =new HashSet<>();
    130.     EntryChunk chunk =new EntryChunk();
    131.     for(int chunkId =1; chunkId < size(); chunkId++){
    132.       readChunk(chunk, chunkId);
    133.       if(chunk.getPart()!=0){
    134.         continue;
    135.       }
    136.  
    137.       // Check to make sure that the start of a file isn't mentioned twice in the cache. If it is
    138.       // then we can't be sure which chunk is the actual start to the file.
    139.       int hash = MortonCode.mortonCode2i(chunk.getType(), chunk.getEntryId());
    140.       if(hashes.contains(hash)){
    141.         thrownewIllegalStateException(
    142.           "Found multiple chunks which describe the start of an entry; "+ chunk.getType()+
    143.             ", "+ chunk.getEntryId()+".");
    144.       }
    145.       hashes.add(hash);
    146.  
    147.       ByteBuffer bb = ByteBuffer.wrap(chunk.getData());
    148.       int compression = bb.get()& 0xff;
    149.       int packedLength = bb.getInt();
    150.  
    151.       compressedLength +=(long) packedLength;
    152.       if(compression !=Container.COMPRESSION_NONE){
    153.         if(chunk.getType()!=5){
    154.           uncompressedLength +=(long) bb.getInt(bb.position());
    155.         }
    156.       }else{
    157.         uncompressedLength +=(long) packedLength;
    158.       }
    159.  
    160.       // Calculate the length of the file from the container header. Table files are not stored
    161.       // with their version because they are internally defined in the format, every other file
    162.       // however is. The last two bytes of the file are reserved for the version.
    163.       int length = packedLength +Container.getHeaderLength(compression);
    164.       if(chunk.getType()!= EntryType.TYPE_TABLE){
    165.         length +=2;
    166.       }
    167.  
    168.       CachePointer pointer =new CachePointer(chunkId, length);
    169.       pointers.put(MortonCode.mortonCode2i(chunk.getType(), chunk.getEntryId()), pointer);
    170.     }
    171.   }
    172.  
    173.   /**
    174.    * Gets the volumes that are mentioned in all of the chunks.
    175.    *
    176.    * @return the volume ids.
    177.    * @throws IOException an I/O exception was encountered.
    178.    */
    179.   public Set<Integer> getMentionedTypes()throwsIOException{
    180.     Set<Integer> volumes =new HashSet<>();
    181.     EntryChunk chunk =new EntryChunk();
    182.     for(int chunkId =1; chunkId < size(); chunkId++){
    183.       readChunk(chunk, chunkId);
    184.       volumes.add(chunk.getType());
    185.     }
    186.     return volumes;
    187.   }
    188.  
    189.   /**
    190.    * Gets the size of the cache in chunks. The size takes into consideration the reserved EOF
    191.    * chunk so this function will always return a value equal to or greater than one.
    192.    *
    193.    * @return the size of the cache.
    194.    */
    195.   publicint size()throwsIOException{
    196.     return(int)(data.length()/ EntryChunk.LENGTH);
    197.   }
    198. }
    199.  
    200.  
    « Last Edit: April 28, 2016, 04:37:18 AM by _nova »
    Runescape Gambling

     

    Copyright © 2017 MoparScape. All rights reserved.
    Powered by SMFPacks SEO Pro Mod |
    SimplePortal 2.3.5 © 2008-2012, SimplePortal