Thread: C++ Exercises

This is something I've been working on for some students.

Let me know if you want more information.

Soma

Our “Group 3735928495” programmers need a secure, clean, and consistent API to examine, modify, and produce “Awesome Virtual File System” formatted image files in order to merge support for our legacy tools into our exciting new productivity suite.

Our new productivity suite utilizes our new and improved “AVFS Blue” file format, but we can't very well forgot our legacy customers! You will need to support our classic “AVFS” files for embedded system, our “AVFS” modern versions from the earliest publicly released variant “1.3” to last years “3.0”, and the now irresistible “Blue”.

Your job, should you choose to accept it, is to provide a modern C++ API to process the “Awesome Virtual File System” file formats and produce a range of developer tools facilitating customer migration to our exciting new productivity suite.



We expect the following general functionality:

“Endian Agnostic” Target Source
“Version Independent” File/Directory Access
“Version Independent” File/Directory Name Searching
“Version Independent” File/Directory Contents Searching
“Version Reduction Tagging” (Invalid Version/STATUS Combinations)
“Version Reduction Adapters” (NAME/STATUS/BLOCK Adapters)
“Version Mirroring” (Version Combined Images)
“Automatic Extended Field Updates”



We expect the following additional functionality for “AVFS Embedded” (Version 0.9):

“Endian Agnostic” File IO

We expect the following additional functionality for “AVFS Classic” (Version 1.3):

“STATUS” Set/Clear (Hidden/System/Archival)
“Reserve” Set/Clear (Block Reserve)
“Owner ID” Set/Clear (String)

We expect the following additional functionality for “AVFS Modern” (Version 2.0):

“File Optimizing” (Mirror File/Encode Once)
“Group ID” Set/Clear (String)

We expect the following additional functionality for “AVFS Ultimate” (Version 3.0):

“File Patching” (Override Blocks)
“Block Optimizing” (Mirror Blocks/Encode Once)

We expect the following additional functionality for “AVFS Blue” (Version 4.0):

“File Versioning” (Override Version Stack)
“File Tagging” (Thumbnail/Terms/Version)
“File MTSID” (String Field ID)



We expect the following tools:

“Endian Conversion” (“AVFS Embedded”)
“File Optimizing” (“AVFS Modern”)
“Block Optimizing” (“AVFS Ultimate”)
“Set Owner” (“AVFS Classic”)
“Set Group” (“AVFS Modern”)
“Set Thumbnail” (“AVFS Blue”)
“Set Terms” (“AVFS Blue”)
“Set Version” (“AVFS Blue”)
“Set Field” (“AVFS Blue”)
“Remove Extended Fields” (“AVFS Blue”)
“File/Directory Name Search Optimizing” (“AVFS Classic”)
“Terms Search Optimizing” (“AVFS Blue”)
Add “Term Search” File (“AVFS Blue”)
Arbitrary Conversion Between “AVFS” Images (General)
Produce Directory From Image (General)
Produce Image From Directory (General)
Format Image (General)
Add File (General)
Erase File (General)
Add Directory (General)
Erase Directory (General)

Fairly complex and large project i'd say.

O_o

No. It really isn't. It is fairly complex but rather small. My aim is project that would take a novice designer with an intermediate level C++ programming knowledge around 255 hours over four months.* I've been trying to tweak the requirements, format, and "landmarks" to accommodate that target.

I'll study the info a bit and see what i can do.

Enjoy, but realize that this is solely a tutorial project. It has nothing to do with any "real world" project.** Consider the group name: "3735928495" is "0xDeadBeaf".

I'll spare the details, but you may consider me acting as a "private tutor" and this tutorial project a significant tool I'm using in that role.

Don't hesitate to send me more about it if you have.

I have everything. I'm designing it! I just haven't finalized a few details and polished my notes for public consumption.

Which are the file formats you're talking about?

There are five distinct file formats corresponding to the five major "AVFS" versions. You may consider these formats virtual file systems in the like of "ISO9660" images. (This the standard format of CD and many DVD discs.)

Let '*' be a null byte marker.
Let '$' be a null "octaword" (16 byte) marker.
Let '[??]' be a "double word" "little endian" value where '?' is a digit.
Let '!?' be a "word" "little endian" value where '?' is a digit.
Let '!!' be a "word" "little endian" value of "0xFFFF".

Let us assume we have a file system with one file in the root directory named "Test.txt" having the contents "Hello, World!".

Take a moment to consider the following fake binary file:

Code:

(Image Header [Block: 0])
AVFS******[01]!1 (Image Block Header)
$$$$$$$$$$$$$$$$ (Unused/Reserved)
$$$$$$$$$$$$$$$  (Unused/Reserved)

(Directory Table {Root} [Block: 1])
AVFS******[01]!! (Directory Block Header)
?.********[01]!2 (Directory Entry)
$$$$$$$$$$$$$$$$ (Unused Directory Entry Area)
$$$$$$$$$$$$$$   (Unused Directory Entry Area)

(Directory Table {Special '.' Directory} [Block: 2])
?.********[01]!! (Directory Block Header)
Test***txt[13]!3 (File Entry)
$$$$$$$$$$$$$$$$ (Unused File Entry Area)
$$$$$$$$$$$$$$   (Unused File Entry Area)

(Data Table {Test.txt} [Block: 3])
Test***txt[13]!! (File Entry Header)
Hello, World!*** (File Data Storage Area)
$$$$$$$$$$$$$$$$ (Unused File Data Storage Area)
$$$$$$$$$$$$$$   (Unused File Data Storage Area)

The information in that code quote at your last post, what does it represent?

Except for the fact that I removed too many of my meandering notes, the post represents all you need to write a tool capable or reading, modifying, and producing "AVFS Embedded" files (images). The description hasn't been polished.

The version I posted is modified form my original notes of the first version. I modified it, as I said, because the "bonus" tool set (the "undeleter" and seek optimizing) became complicated enough that I could do no standard testing from within my own code. (The modifications are trivial, but not required to fit a specific representation.)

Does AVFS have anything to do with this?

No. This tutorial project has nothing to do with that project. The shared acronym is purely coincidence.

Soma

* 255 = 17(Weeks) * 5(Days/Week) * 3(Hours/Day)

** Each file format introduces certain techniques commonly used in a wide variety or real world formats. These shared techniques are the only thing this tutorial project has in common with "real world" projects.

Every file format from the tutorial project introduces "real world" issues, techniques, and tools.

Why every Title has to be 10 bytes long?

In this case, I intend to introduce fixed formats common to some file systems.

This is a modification to "FAT" and the classic "8.3" naming scheme.

Why every block has to be 512 bytes in size?

It is common for many file systems to operate on fixed sized "chunks" whether it be sectors, pages, extents, or something else entirely. The size of the "chunks" are generally chosen at the time of format and never again changed.

Using 512 byte blocks as the smallest and largest operating unit simplifies this introductory material.

The way you describe for the file system's image, block indexing, i believe it is very hard to maintain.

^_^

You should see the variable sized extent pools I'm targeting for the "AVFS Blue" format.

Direct indexing of fixed size blocks is the simplest form of addressing. The form of addressing and indirection you are used to operating on from C++ pointers and references do the same thing for memory as the file format does for image blocks.

It isn't "hard to maintain", but some operations can be expensive. Consider the "trade offs" of arrays versus linked lists versus binary trees.

How can i apply change or delete techniques without loading the whole image on memory ( which would be next to impossible in the case of a large image file ) ?

O_o

That would be something you are supposed to "discover" for yourself. I can't very well just tell you exactly what to do.

What specifically are you having trouble with? Why do you think it would be necessary to load the entire file in memory?

As with most anything, some level of caching improves performance, but you absolutely do not need to have the entire image in memory to create, modify, or delete files.

Consider these questions as they may provide some insight into a potential implementation:

What is the least number of bytes necessary to record only the meta-information necessary for "ready processing" of any one file in the largest valid "AVFS Embedded" image?

What is the least number of bytes necessary to record only the meta-information necessary for "ready processing" of every file in the largest valid "AVFS Embedded" image?

What is the least number of bytes necessary to record the complete meta-information of any one file in the largest valid "AVFS Embedded" image?

What is the least number of bytes necessary to record the complete meta-information of every file in the largest valid "AVFS Embedded" image?

For the purposes of these questions you may consider "ready processing" as having "just obtained" a pointer to a valid and fully constructed `std::fstream' object targeting a specific file in the "AVFS Embedded" image.

Enjoy.

Soma

So with all that, are you telling me to consider an image as RAM, where its size stays fixed and i "allocate" and "free" it?

No. I'm not telling you to consider the image as RAM. I'm telling you to consider the problem of operating on these files as being similar to the problem of operating on mutually linked structures.

Because i've been thinking of a way to reduce its size when deleting, which is very difficult do to the fact that i should iterate all entries and change their indexing.

O_o

It seems very likely that you are missing some potential. I strongly advise you to discuss the approach you intend with me before you continue.

That can't be done in public. (I don't like cheaters.) If you want counsel at this level for this issue send me a private message describing your "delete with space optimization" mechanism. I will not tell you what to do, but I may be able to guide you to some aspects of the image format you may have missed. If you do send me this message, please attempt to answer the four questions I asked in my last post. Your answers will help me gauge your understanding of the file format and the usefulness of those questions to others.

That said, in the "real world", tools that operate on virtual file system images will almost always separate the duties of file removal and space optimization. Such tools will essentially perform two passes when performing in an "delete with space optimization" mode. There are some really good reasons for this approach.

Soma